Tree DFS (In/Pre/Post)

The Intuition

Tree DFS visits every node by recursively descending one branch fully before backtracking to the next. Three traversal orderings differ only in when the current node is processed relative to its subtrees:

Preorder (root, left, right): process the node, then recurse left, then right. Used for serialization, copying a tree, and producing prefix expressions.
Inorder (left, root, right): recurse left, process the node, recurse right. On a BST this produces values in sorted order, which is why inorder is the standard tool for BST validation (LC 98) and finding the kth smallest element (LC 230).
Postorder (left, right, root): recurse left, recurse right, process the node. Used when subtree results must be combined, such as computing subtree sums, deleting a tree, or evaluating postfix expressions.

The recursion stack handles backtracking implicitly: every recursive call pushes a frame, every return pops one. Total time is O(n) for any traversal; space is O(h) for the recursion stack, where h is tree height (O(log n) balanced, O(n) worst case).

A common DFS pattern in interviews is the post-order with subtree return value. The recursive call returns information about the subtree (height, size, max path sum, whether it's balanced), and the parent combines its children's returns to compute its own answer. This pattern solves diameter (LC 543), max path sum (LC 124), is balanced (LC 110), and many subtree-size problems. The function typically returns one value to its parent while side-effectfully updating a global best variable when a subtree-internal answer is better than any seen so far.

Iterative implementations use an explicit stack. Iterative inorder is the trickiest: push nodes while descending left, pop to visit and emit, then descend right from the popped node's right child. The recursion-based code is almost always shorter and clearer, so prefer it unless stack-depth is a real concern.

When to use

Serialization, expression evaluation, BST validation, tree construction from traversals, path sum problems, or any tree problem requiring recursive decomposition.

When NOT to use

Need shortest path in a tree (use BFS)
Need level-order information
Tree is extremely deep and might overflow the call stack (use iterative BFS)

Pattern Recognition

path sumtree traversalvalidate BST

Edge Cases

empty tree
single node
skewed tree

Practice Problems

EasyBinary Tree Inorder Traversal

EasyMaximum Depth of Binary Tree

EasyPath Sum

MediumValidate Binary Search Tree

EasyDiameter of Binary Tree

Key Points

•Pre-order: process node BEFORE children (root-left-right)
•In-order: process node BETWEEN children (left-root-right). Gives sorted order in BST
•Post-order: process node AFTER children (left-right-root)
•Recursive approach mirrors the traversal naturally
•Space is O(h) where h = tree height; O(log n) balanced, O(n) worst case

Code Template

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    """Pre-order: root -> left -> right."""
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    """In-order: left -> root -> right (sorted for BST)."""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    """Post-order: left -> right -> root."""
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Iterative in-order using stack
def inorder_iterative(root):
    result, stack = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func preorder(root *TreeNode) []int {
    // Pre-order: root -> left -> right.
    if root == nil {
        return nil
    }
    result := []int{root.Val}
    result = append(result, preorder(root.Left)...)
    result = append(result, preorder(root.Right)...)
    return result
}

func inorder(root *TreeNode) []int {
    // In-order: left -> root -> right (sorted for BST).
    if root == nil {
        return nil
    }
    result := inorder(root.Left)
    result = append(result, root.Val)
    result = append(result, inorder(root.Right)...)
    return result
}

func postorder(root *TreeNode) []int {
    // Post-order: left -> right -> root.
    if root == nil {
        return nil
    }
    result := postorder(root.Left)
    result = append(result, postorder(root.Right)...)
    result = append(result, root.Val)
    return result
}

public List<Integer> preorder(TreeNode root) {
    // Pre-order: root -> left -> right.
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.add(root.val);
    result.addAll(preorder(root.left));
    result.addAll(preorder(root.right));
    return result;
}

public List<Integer> inorder(TreeNode root) {
    // In-order: left -> root -> right (sorted for BST).
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    result.addAll(inorder(root.left));
    result.add(root.val);
    result.addAll(inorder(root.right));
    return result;
}

// Iterative in-order using stack
public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result;
}

Common Mistakes

Confusing pre/in/post ordering for specific problems
Not handling the null/None base case
Forgetting that in-order on BST gives sorted output

Related Patterns

CrackingWalnuts

TreesTemplate 1 of 5

TreeBasicO(n) time, O(h) space