Tree traversals

• Tree traversals
  • Depth-first (recursion)
  • Breadth-first (level by level)
  • Cost

§Tree traversals

Most tree questions start with visiting every node in some order.

§Depth-first (recursion)

• Pre-order: node, then left, then right. Use it to copy a tree or print it top-down.
• In-order: left, then node, then right. On a binary search tree this gives the values in sorted order, a favorite interview fact.
• Post-order: left, then right, then node. Use it to delete a tree or compute sizes (children first).

var root = new Tree(2, new Tree(1, null, null), new Tree(3, null, null));
var order = new List<int>();
InOrder(root, order);
Console.WriteLine(string.Join(" ", order));

static void InOrder(Tree? t, List<int> order)
{
    if (t == null) return;
    InOrder(t.Left, order); order.Add(t.Value); InOrder(t.Right, order);
}

It prints 1 2 3: in-order on a BST is sorted.

§Breadth-first (level by level)

Use a queue: take a node out, add its children at the back. Use it for “shortest path in steps”, “print level by level”, or “nodes closest to the root”.

var root = new Tree(1, new Tree(2, new Tree(4, null, null), null), new Tree(3, null, null));
var queue = new Queue<Tree>(new[] { root });
var visited = new List<int>();
while (queue.Count > 0)
{
    var t = queue.Dequeue(); visited.Add(t.Value);
    if (t.Left != null) queue.Enqueue(t.Left);
    if (t.Right != null) queue.Enqueue(t.Right);
}
Console.WriteLine(string.Join(" ", visited));

It prints 1 2 3 4: the root, then its children, then the next level.

§Cost

Every traversal visits each node once: O(n) time. Memory: recursion uses O(h), where h is the tree’s height (O(log n) if balanced, O(n) if it is a chain); breadth-first keeps up to one full level in the queue.

Read more: https://www.geeksforgeeks.org/dsa/tree-data-structure/

#tip · TIP-064