Tree traversals: pre, in, post and level order
Visit every node of a tree in pre-order, in-order, post-order and level order, recursively and with an explicit stack or queue, and know which order solves which problem.
Depth first: pre, in and post
Pre-order: node, then left subtree, then right subtree. In-order: left subtree, then node, then right subtree. Post-order: left subtree, then right subtree, then node.
var root = new Node(8, new Node(4, new Node(2, new Node(1)), new Node(6, null, new Node(7))), new Node(12, new Node(10), new Node(14))); var pre = new List<int>();var ino = new List<int>();var post = new List<int>();PreOrder(root, pre);InOrder(root, ino);PostOrder(root, post);Console.WriteLine("Pre: " + string.Join(" ", pre));Console.WriteLine("In: " + string.Join(" ", ino));Console.WriteLine("Post: " + string.Join(" ", post)); static void PreOrder(Node? n, List<int> result){ if (n is null) return; result.Add(n.Value); // node first PreOrder(n.Left, result); PreOrder(n.Right, result);} static void InOrder(Node? n, List<int> result){ if (n is null) return; InOrder(n.Left, result); result.Add(n.Value); // node in the middle InOrder(n.Right, result);} static void PostOrder(Node? n, List<int> result){ if (n is null) return; PostOrder(n.Left, result); PostOrder(n.Right, result); result.Add(n.Value); // node last} record Node(int Value, Node? Left = null, Node? Right = null);Pre: 8 4 2 1 6 7 12 10 14 In: 1 2 4 6 7 8 10 12 14 Post: 1 2 7 6 4 10 14 12 8
Without recursion: an explicit stack
Stack<T> yourself instead, which never overflows the call stack on a very deep tree. For pre-order, push the right child before the left, so the left one comes off the stack first:
// same root and Node record as aboveConsole.WriteLine(string.Join(" ", PreOrderIterative(root))); static List<int> PreOrderIterative(Node root){ var result = new List<int>(); var stack = new Stack<Node>(); stack.Push(root); while (stack.Count > 0) { var n = stack.Pop(); result.Add(n.Value); if (n.Right is not null) stack.Push(n.Right); // right first… if (n.Left is not null) stack.Push(n.Left); // …so left is popped first } return result;}8 4 2 1 6 7 12 10 14
Breadth first: level order
// same root and Node record as aboveLevelOrder(root); static void LevelOrder(Node root){ var queue = new Queue<Node>(); queue.Enqueue(root); int level = 0; while (queue.Count > 0) { int count = queue.Count; // nodes on this level var line = new List<int>(); for (int i = 0; i < count; i++) { var n = queue.Dequeue(); line.Add(n.Value); if (n.Left is not null) queue.Enqueue(n.Left); if (n.Right is not null) queue.Enqueue(n.Right); } Console.WriteLine($"Level {level++}: {string.Join(" ", line)}"); }}Level 0: 8 Level 1: 4 12 Level 2: 2 6 10 14 Level 3: 1 7
Post-order in action: evaluating an expression
Expr e = new Op('*', new Op('+', new Num(3), new Num(4)), new Op('-', new Num(10), new Num(8))); Console.WriteLine(Show(e));Console.WriteLine(Eval(e)); static string Show(Expr e) => e switch // in-order{ Num n => n.Value.ToString(), Op o => $"({Show(o.Left)} {o.Symbol} {Show(o.Right)})", _ => throw new ArgumentException("Unknown node")}; static double Eval(Expr e) => e switch // post-order: children first{ Num n => n.Value, Op o => Apply(o.Symbol, Eval(o.Left), Eval(o.Right)), _ => throw new ArgumentException("Unknown node")}; static double Apply(char op, double a, double b) => op switch{ '+' => a + b, '-' => a - b, '*' => a * b, '/' => a / b, _ => throw new ArgumentException($"Unknown operator {op}")}; abstract record Expr;record Num(double Value) : Expr;record Op(char Symbol, Expr Left, Expr Right) : Expr;((3 + 4) * (10 - 8)) 14
Which order for which job?
| Order | Typical uses |
|---|---|
HasPathSum(Node? n, int target) that returns true if some path from the root down to a leaf has values adding up to target. For the tree in this lesson, the root-to-leaf sums are 15 (8-4-2-1), 25 (8-4-6-7), 30 (8-12-10) and 34 (8-12-14), so 25 → True and 20 → False.
Show a hint
Show the solution
var root = new Node(8, new Node(4, new Node(2, new Node(1)), new Node(6, null, new Node(7))), new Node(12, new Node(10), new Node(14))); Console.WriteLine(HasPathSum(root, 25));Console.WriteLine(HasPathSum(root, 20));Console.WriteLine(HasPathSum(root, 34)); static bool HasPathSum(Node? n, int target){ if (n is null) return false; int remaining = target - n.Value; if (n.Left is null && n.Right is null) return remaining == 0; // a leaf return HasPathSum(n.Left, remaining) || HasPathSum(n.Right, remaining);} record Node(int Value, Node? Left = null, Node? Right = null);True False True
Remember
Pre-order: node, left, right. In-order: left, node, right. Post-order: left, right, node. Level order uses a queue and visits the tree level by level. All traversals are O(n); recursion uses O(height) stack, an explicit Stack<T> avoids stack overflow. In-order of a BST is sorted; post-order suits work that needs the children’s results first.