Tree Traversal and Tree Problems Questions

Problems and patterns involving tree structures, including traversal orders such as in order, pre order, and post order, recursive and iterative traversal techniques, computing tree height and depth, lowest common ancestor solutions, path sum and root to leaf problems, and balancing considerations. Candidates should be able to reason about recursion depth, stack based iterative solutions, and analyze time and memory complexity for tree algorithms.

MediumTechnical

38 practiced

You are adding two helpers to a tree library: one reports the maximum root-to-leaf distance, and the other reports how far a specific node is from the root. How would you implement both in Python, and what conventions would you settle on up front so the API is not ambiguous?

Sample Answer

**Conventions first**I would define `height` as the number of edges on the longest path from a node to a leaf. That makes an empty tree height `-1` and a leaf height `0`. I would define `depth` as the number of edges from the root to a node, so the root has depth `0`. That keeps the API consistent.

python

def tree_height(root):
    if root is None:
        return -1
    return 1 + max(tree_height(root.left), tree_height(root.right))


def node_depth(root, target):
    def dfs(node, depth):
        if node is None:
            return None
        if node is target:
            return depth
        left = dfs(node.left, depth + 1)
        if left is not None:
            return left
        return dfs(node.right, depth + 1)

    return dfs(root, 0)

**Worked example**If the tree is `10 -> 4 -> 2`, then `tree_height(root)` is `2`, `node_depth(root, 10)` is `0`, and `node_depth(root, 2)` is `2`.

**API design choice**I would return `None` if the target node is not present, rather than guessing. That makes the behavior explicit and avoids ambiguity.

HardTechnical

41 practiced

Given two nodes in a binary tree, return their lowest common ancestor. The tree is not guaranteed to be a BST, and the input may reference nodes that are not present. How would you design the function so it never reports an ancestor unless both targets are actually in the tree?

Sample Answer

**Design**I would compare nodes by identity, not by value, because duplicate values make value-based matching ambiguous. To avoid false positives, the helper should return both the candidate ancestor and whether each target was actually found.

python

def lowest_common_ancestor(root, p, q):
    def dfs(node):
        if node is None:
            return None, False, False

        left_lca, left_has_p, left_has_q = dfs(node.left)
        if left_lca is not None and left_has_p and left_has_q:
            return left_lca, True, True

        right_lca, right_has_p, right_has_q = dfs(node.right)
        if right_lca is not None and right_has_p and right_has_q:
            return right_lca, True, True

        has_p = left_has_p or right_has_p or node is p
        has_q = left_has_q or right_has_q or node is q

        if has_p and has_q:
            return node, True, True

        return None, has_p, has_q

    lca, has_p, has_q = dfs(root)
    return lca if has_p and has_q else None

**Worked example**If `p` is in the left subtree and `q` is in the right subtree, the root becomes the LCA. If `q` is missing from the tree, the final `has_q` flag stays false, so the function returns `None` instead of a misleading ancestor.

**Why this is safe**The function only reports an ancestor when both targets are confirmed present in the tree.

HardTechnical

40 practiced

You are reviewing a function that decides whether a binary tree is height-balanced. The current code recomputes subtree heights over and over, and it becomes slow on a skewed input. How would you rewrite it so each subtree is processed once, and how would you stop the recursion early when imbalance is detected?

Sample Answer

**Idea**The slow part in the original version is recomputing heights for the same subtree many times. I would make one DFS return the height of a subtree, and use `-1` as a sentinel meaning unbalanced. That lets me stop early as soon as imbalance is detected.

python

def is_balanced(root):
    def height(node):
        if node is None:
            return 0

        left_h = height(node.left)
        if left_h == -1:
            return -1

        right_h = height(node.right)
        if right_h == -1:
            return -1

        if abs(left_h - right_h) > 1:
            return -1

        return max(left_h, right_h) + 1

    return height(root) != -1

**Worked example**For a skewed chain `1 -> 2 -> 3 -> 4`, the imbalance is detected near the top once the left and right subtree heights differ by more than 1, and the `-1` bubbles upward immediately.

**Why this is better**Each subtree is processed once, so the runtime becomes O(n) instead of repeatedly revisiting nodes. Space is O(h) for the recursion stack.

MediumTechnical

62 practiced

Recursion is off the table because the tree may be too deep. In Python, implement a traversal that visits both children before the node itself and returns the values in that order. Walk through how your stack state changes as the algorithm runs.

Sample Answer

**Approach**This is postorder traversal, which means left child, right child, then node. Since recursion is off the table, I would use an explicit stack and a `last_visited` pointer to know when a node's right subtree has already been processed.

python

def postorder_traversal(root):
    result = []
    stack = []
    current = root
    last_visited = None

    while current is not None or stack:
        if current is not None:
            stack.append(current)
            current = current.left
        else:
            peek = stack[-1]
            if peek.right is not None and last_visited is not peek.right:
                current = peek.right
            else:
                result.append(peek.val)
                last_visited = stack.pop()

    return result

**Stack walk-through**For root 1 with left 2 and right 3:- Push 1, then push 2.- Node 2 has no children, so pop and output 2.- Back at 1, move to 3, push 3, then pop and output 3.- Finally pop and output 1.

**Why this works**The stack always holds the path to the current node. `last_visited` prevents revisiting a right subtree after it has already been processed. Time is O(n), space is O(h), where h is tree height.

EasyTechnical

34 practiced

You are given the root of a binary tree in Python. Implement a function that returns the node values in left, then node, then right order. After you write the recursive version, explain how you would handle an empty tree and why the solution may fail on a pathologically deep input.

Sample Answer

**Approach**Inorder traversal means: visit the left child, then the node itself, then the right child. I would use recursion because it matches the tree structure naturally.

python

def inorder_traversal(root):
    result = []

    def dfs(node):
        if node is None:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)

    dfs(root)
    return result

**Worked example**For a tree with root 2, left child 1, and right child 3, the result is `[1, 2, 3]`.

**Empty tree**If `root` is `None`, the helper returns immediately and the answer is an empty list. That is the correct result because there are no nodes to visit.

**Why recursion can fail**Python has a finite call stack. On a pathologically deep tree, such as a chain of 10,000 nodes, recursive calls can raise `RecursionError` even though the logic is correct. In that case, I would switch to an iterative traversal with an explicit stack.

Unlock Full Question Bank

Get access to hundreds of Tree Traversal and Tree Problems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.