Questions tagged [tree-traversal]

Challenge related to the concept of trees present in graph theory.

Filter by
Sorted by
Tagged with
6
votes
4answers
264 views

Regrowing trees

Background Here you have another work-inspired challenge, but from my wife's work in this case. Imagine you have a service that returns the list of nodes in a tree structure (much like the files and ...
7
votes
3answers
131 views

Rooting for Trees With the Right Nodes

Background A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent ...
8
votes
2answers
197 views

Compute the height of a radix tree

Introduction A radix tree, also known as compressed trie or compressed prefix tree, is a tree-like data structure for storing a set of strings. The edges of the tree are labeled by nonempty strings, ...
11
votes
7answers
395 views

Is it a Linearized Tree? (Breadth-first Edition)

Background An unlabelled tree may look like this: o / | \ o o o | / \ o o o To linearize this tree, we first label each node ...
11
votes
3answers
361 views

Pre-order + post-order to in-order

Task Given the pre-order and post-order traversals of a full binary tree, return its in-order traversal. The traversals will be represented as two lists, both containing n distinct positive integers,...
15
votes
7answers
389 views

Evaluate a minimax tree

Alice and Bob are playing a little game. First, they draw a tree from a root node (indicated by a thick dot), with no internal nodes, with numbers at the leaves. Any node may have any number of ...
12
votes
2answers
300 views

Creasing for Loot

Introduction After a long battle, you have managed to defeat a Sphinx in a contest of riddles. The Sphinx, impressed with your skill, wishes to give you a reward commensurate with your cleverness, ...
13
votes
1answer
518 views

mtDNA mutation tree

Background: MtDNA is a part of the human DNA that is passed from a mother to a child and it rarely mutates. Since this is true for all humans it is possible to create a huge tree that visualize how ...
6
votes
5answers
2k views

Convert binary search tree into ordered linked list

Write the shortest possible program that turns a binary search tree into an ordered doubly-linked list, by modifying the pointers to the left and the right children of each node. Arguments: a pointer ...
2
votes
14answers
2k views

Traverse a directory tree and output a list of all files

Write the shortest code that traverses a directory tree and outputs a flat list of all files. It should traverse the whole directory tree The order in which it enters sub-directories doesn't matter ...
1
vote
1answer
480 views

How can I make this program smaller? [closed]

I am trying my hand at writing super small programs. I wrote a simple "tree" display program for showing a graphical representation of a folder hierarchy. I have made it small in all the ways I can ...
4
votes
5answers
1k views

Tree traversal: Depth-first search

Write the shortest code that traverses a tree, depth-first. Input Any programmatical structure found in your language of choice: lists, tuples, queues etc. Output A list of "names" of the nodes in ...
11
votes
8answers
6k views

Binary tree encoding

Let's suppose you have a complete binary tree (i.e. each internal node has exactly two non empty descendants). Each node contains a nonzero integer. You are given the task of encoding and decoding the ...
7
votes
5answers
792 views

Tree traversal.

Write the shortest code that traverses a tree, breadth-first. Input any way you like Output a list of "names" of the nodes in correct order.