Questions tagged [tree-traversal]
Challenge related to the concept of trees present in graph theory.
22 questions
20
votes
12
answers
2k
views
Recognize a counting tree
Let a counting tree be a rooted tree in which every node is labeled with the number of descendants it has.
We can represent such trees as ragged lists with each node being represented by a list ...
- 103k
3
votes
0
answers
181
views
Build a file/directory tree [closed]
Task
In this challenge, your task is to write a program or function which takes an array of paths with an additional boolean indicating it is a file or directory and outputs a file/directory tree in ...
- 161
8
votes
4
answers
325
views
Your trees need to be rerooted
In graph theory a tree is just any graph with no cycles. But in computer science we often use rooted trees. Rooted trees are like trees except they have one specific node as the "root", ...
- 103k
23
votes
14
answers
1k
views
Scan a ragged list
hgl has a "scan" function called sc. What it does in general is a little bit abstract, so we will just talk about one specific way you can use it.
If we ...
- 103k
13
votes
11
answers
1k
views
The longest consecutive traversal possible (number of edges)
A truck fleet dispatcher is trying to determine which routes are still accessible after heavy rains flood certain highways. During their trips, trucks must follow linear, ordered paths between ...
- 337
9
votes
1
answer
306
views
Branch Out - Monkey Edition
The Monkey has swung home to find his tree all in pieces.
He likes order and scoops up all his 'tree-parts' and sets them out in 3 groups.
The Monkey's ...
- 261
5
votes
8
answers
709
views
Shortest Program To Find Lowest Common Ancestor of Two Nodes in a Binary Tree
Any two separate nodes in a binary tree have a common ancestor, which is the root of a binary tree. The lowest common ancestor(LCA) is thus defined as the node that is furthest from the root and that ...
- 665
18
votes
11
answers
6k
views
Check If a Binary Tree is Balanced
For each node in a balanced binary tree, the maximum difference in the heights of the left child subtree and the right child subtree are at most 1.
The height of a binary tree is the distance from the ...
- 665
7
votes
4
answers
371
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 ...
- 13k
7
votes
3
answers
215
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 ...
- 16.4k
9
votes
2
answers
423
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, ...
- 43.2k
12
votes
7
answers
815
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 ...
- 26.4k
15
votes
5
answers
764
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,...
- 69.7k
15
votes
7
answers
616
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 ...
- 39.4k
12
votes
2
answers
350
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, ...
- 1,205
14
votes
1
answer
645
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 ...
- 1,796
7
votes
5
answers
5k
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 ...
user26458
1
vote
14
answers
3k
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
...
2
votes
1
answer
565
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 ...
- 21
5
votes
12
answers
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 ...
13
votes
8
answers
7k
views
Binary tree encoding [closed]
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 ...
- 6,140
4
votes
5
answers
1k
views
Tree traversal. [closed]
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.
- 5,550