Trees

DFS (Depth-First Search)

TimeO(V + E) SpaceO(h)

Think of exploring a maze. You pick a path and follow it all the way to a dead end. Then you backtrack to the last junction and try a different path. You keep going deeper first, only widening your search when you’ve exhausted a branch.

When to use it: Tree traversals (preorder, inorder, postorder), path-finding where you need to explore all paths, checking tree properties (height, balance, symmetry), and any recursive tree problem.

Key insight: DFS naturally maps to recursion — the call stack handles backtracking for you. The three traversal orders (pre/in/post) differ only in when you process the current node relative to its children.

Common trap: Stack overflow on very deep trees. For trees with depth up to 10^5, use an iterative approach with an explicit stack instead of recursion.

# Preorder: root, left, right
function preorder(node):
    if node == null: return
    process(node)
    preorder(node.left)
    preorder(node.right)

# Inorder: left, root, right (gives sorted order in BST)
function inorder(node):
    if node == null: return
    inorder(node.left)
    process(node)
    inorder(node.right)

# Postorder: left, right, root (useful for deletion, calculating heights)
function postorder(node):
    if node == null: return
    postorder(node.left)
    postorder(node.right)
    process(node)

# Iterative DFS using explicit stack (preorder)
function iterativeDFS(root):
    if root == null: return
    stack = [root]

    while stack is not empty:
        node = stack.pop()
        process(node)

        if node.right != null:       # push right first so left is processed first
            stack.push(node.right)
        if node.left != null:
            stack.push(node.left)

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


def preorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)


def inorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)


def postorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]


def max_depth(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


def has_path_sum(root: TreeNode | None, target: int) -> bool:
    """Check if any root-to-leaf path sums to target."""
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target
    return (has_path_sum(root.left, target - root.val) or
            has_path_sum(root.right, target - root.val))


def iterative_inorder(root: TreeNode | None) -> list[int]:
    """Iterative inorder using an explicit stack."""
    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

Problem: Given a binary tree and a target sum, determine if there exists a root-to-leaf path where the values sum to the target.

How would you approach this?

Answer: This is DFS because you need to explore complete root-to-leaf paths. At each node, subtract its value from the target and recurse on children. At a leaf, check if the remaining target equals the leaf's value.

Problem: Given a binary tree, determine if it is height-balanced (left and right subtrees of every node differ in height by at most 1).

How would you approach this?

Answer: This is postorder DFS. Compute the height bottom-up: for each node, get the heights of left and right subtrees (computed recursively), check if they differ by more than 1, and return -1 to short-circuit if unbalanced.

Time: O(V + E) where V is the number of nodes and E is edges. In a tree, E = V - 1, so O(V). Every node is visited exactly once during the traversal.

Space: O(h) where h is the height of the tree. This is the maximum depth of the recursion stack (or explicit stack). For a balanced tree h = O(log n); for a skewed tree h = O(n).