# Questions tagged [tree-traversal]

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

16 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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,...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...