Visualization: Tree Traversal Paths | Data Structures

Practice tracing recursive traversal paths and building visual mental models of tree execution stacks.

Problem 1: Maximum Depth of Binary Tree

Specification

Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to leaf).

Recursive Solution (Post-Order Intuition)

The depth of any node is:

1 + max(depth(left), depth(right))

fun maxDepth(root: TreeNode<Int>?): Int {
    if (root == null) return 0
    val leftDepth = maxDepth(root.left)
    val rightDepth = maxDepth(root.right)
    return 1 + maxOf(leftDepth, rightDepth)
}

Call Stack Visualization for:
      [ 1 ]
     /     \
   [ 2 ]   [ 3 ]
             \
             [ 4 ]

maxDepth(4) returns 1
maxDepth(3) returns 1 + max(0, 1) = 2
maxDepth(2) returns 1 + max(0, 0) = 1
maxDepth(1) returns 1 + max(1, 2) = 3

Problem 2: Invert / Mirror a Binary Tree

Specification

Invert a binary tree so that left and right children are swapped at every node.

       [ 4 ]                       [ 4 ]
      /     \                    /     \
    [ 2 ]   [ 7 ]    ====>      [ 7 ]   [ 2 ]
   /   \   /   \              /   \   /   \
 [ 1 ] [ 3 ][ 6 ] [ 9 ]       [ 9 ] [ 6 ][ 3 ] [ 1 ]

Implementation

fun invertTree(root: TreeNode<Int>?): TreeNode<Int>? {
    if (root == null) return null

    // Swap left and right child references
    val temp = root.left
    root.left = invertTree(root.right)
    root.right = invertTree(temp)

    return root
}

Problem 3: Lowest Common Ancestor (LCA) in a BST

In a Binary Search Tree, we can exploit the BST ordering property (L < Root < R) to find the Lowest Common Ancestor of two nodes P and Q in O(h) time without searching the entire tree!

fun lowestCommonAncestor(root: TreeNode<Int>?, p: Int, q: Int): TreeNode<Int>? {
    var curr = root
    while (curr != null) {
        if (p < curr.value && q < curr.value) {
            curr = curr.left // Both nodes are in left subtree
        } else if (p > curr.value && q > curr.value) {
            curr = curr.right // Both nodes are in right subtree
        } else {
            return curr // Split point! This is the LCA!
        }
    }
    return null
}

Summary

Most tree problems reduce to a choice between Pre-Order (passing information downward) and Post-Order (aggregating results upward).
In a BST, value comparisons let you eliminate half the tree at every step, yielding logarithmic O(log n) search.