Questions tagged [tree-traversal]

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

Filter by
Sorted by
Tagged with
3
votes
8answers
221 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 ...
16
votes
10answers
4k views

Write The Shortest Program To 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 ...
6
votes
4answers
266 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
133 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
210 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
418 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
375 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
395 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
301 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
521 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
484 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 ...
12
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
803 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.