Binary Tree Interview Problems: Traversals, Views, Diameter and Path Sums

Binary trees are probably the most-asked topic after arrays and strings at product companies, and they are where recursion either clicks or does not. The good news: tree questions are far more uniform than they first look. Once you can answer "what does this function return for a subtree, and how do I combine left and right?", most of them become 10 lines of code.

This guide builds that skill in order: traversals (recursive, iterative and level order), then views, then the "combine children" problems (height, balance, diameter, maximum path sum), then path sums and construction. If recursion itself feels shaky, read recursion for beginners first.

The node definition and the example tree used in dry runs throughout:

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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

The Mental Model: What Does Each Node Return?

For any tree problem, decide which of three shapes it has:

The bottom-up shape has one key refinement: the value a node returns to its parent can differ from the value it contributes to the answer. Diameter and maximum path sum are the famous examples. Spotting that distinction is what interviewers are testing.

Complexity is nearly always O(n) time, because each node is visited once, and O(h) space for recursion, where h is the height: O(log n) for a balanced tree and O(n) for a skewed one. State the skewed worst case; it matters for stack overflow on deep trees.

DFS Traversals: Preorder, Inorder, Postorder

def preorder(root, out):
    if root:
        out.append(root.val)
        preorder(root.left, out)
        preorder(root.right, out)

def inorder(root, out):
    if root:
        inorder(root.left, out)
        out.append(root.val)
        inorder(root.right, out)

def postorder(root, out):
    if root:
        postorder(root.left, out)
        postorder(root.right, out)
        out.append(root.val)

Recursive versions are trivial; the follow-up "now do it without recursion" is where marks are earned.

Iterative Tree Traversals With a Stack

Iterative preorder

Pop a node, visit it, push right then left (so left is processed first).

def preorder_iterative(root):
    if not root:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

Iterative inorder

Go left as far as possible, pushing nodes; pop, visit, then move to the right child.

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }   // slide left
        cur = stack.pop();
        res.add(cur.val);                                          // visit
        cur = cur.right;                                           // then right subtree
    }
    return res;
}

Dry run on the example tree: push 1, 2, 4; pop 4 (visit), right is null; pop 2 (visit), go to 5; push 5, pop 5 (visit); pop 1 (visit), go to 3; push 3, pop 3 (visit), go to 6; push 6, pop 6 (visit). Output 4 2 5 1 3 6. This template is the basis of BST iterators and "kth smallest in a BST" (see BST problems).

Iterative postorder

Two common approaches. The easy one: do a modified preorder (node, right, left) and reverse the output, which gives left, right, node. The "true" one-stack version tracks the last visited node so you know whether you are returning from the right subtree.

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root, lastVisited = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        TreeNode top = stack.peek();
        if (top.right != null && top.right != lastVisited) {
            cur = top.right;                     // right subtree not done yet
        } else {
            res.add(top.val);                    // both subtrees done
            lastVisited = stack.pop();
        }
    }
    return res;
}

def postorder_iterative(root):
    if not root:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)           # node, right, left ...
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return out[::-1]                   # ... reversed = left, right, node

Morris traversal: O(1) extra space

Morris inorder temporarily threads each node's inorder predecessor back to it, then removes the thread. O(n) time, O(1) space, and the tree is restored. It is a "do you know it exists" question more than a "code it" question, but here is the core:

def morris_inorder(root):
    out, cur = [], root
    while cur:
        if not cur.left:
            out.append(cur.val)
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur:
                pred = pred.right
            if not pred.right:          # create thread, go left
                pred.right = cur
                cur = cur.left
            else:                       # thread exists: left done, remove it
                pred.right = None
                out.append(cur.val)
                cur = cur.right
    return out

BFS: Level Order, Zigzag and Width

The key detail in level-order BFS is capturing the queue size at the start of each level, so you know exactly which nodes belong to it.

from collections import deque

def level_order(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):        # exactly the nodes of this level
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

Variants that reuse this loop: zigzag order (reverse every other level, or use a deque and insert at the front on odd levels); average of levels; minimum depth (return the depth of the first leaf found, which BFS finds earliest); maximum width (store each node's position index, children at 2i and 2i + 1, width = last - first + 1, and normalise per level to avoid overflow); and connecting next-right pointers.

Binary Tree Views: Left, Right, Top and Bottom

Views are standard in Indian interview prep sheets (GeeksforGeeks, Striver) and frequently asked at service and product companies alike. The trick is choosing the right key.

Left and right view: key on depth

Right view is the last node of each BFS level (LeetCode 199). With DFS, visit right before left and record the first node seen at each new depth.

def right_side_view(root):
    res = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(res):          # first node seen at this depth
            res.append(node.val)
        dfs(node.right, depth + 1)     # right first for the right view
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return res

On the example tree: right view 1 3 6, left view (swap the two recursive calls) 1 2 4. Note a subtle case: if the right subtree is shorter, deeper nodes from the left subtree appear in the right view, which this code handles automatically.

Top and bottom view: key on horizontal distance

Assign the root horizontal distance (hd) 0; a left child gets hd - 1 and a right child hd + 1. Top view is the first node seen per hd in BFS order; bottom view is the last. BFS is used because it visits shallower nodes first; a plain DFS would get the depth ordering wrong unless it also tracks depth.

public List<Integer> topView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    TreeMap<Integer, Integer> firstAtHd = new TreeMap<>();        // sorted by hd
    Queue<Object[]> q = new ArrayDeque<>();
    q.offer(new Object[]{root, 0});
    while (!q.isEmpty()) {
        Object[] cur = q.poll();
        TreeNode node = (TreeNode) cur[0];
        int hd = (int) cur[1];
        firstAtHd.putIfAbsent(hd, node.val);     // bottom view: use put() instead
        if (node.left != null) q.offer(new Object[]{node.left, hd - 1});
        if (node.right != null) q.offer(new Object[]{node.right, hd + 1});
    }
    res.addAll(firstAtHd.values());
    return res;
}

On the example tree, horizontal distances are: 4 at -2, 2 at -1, 1 and 5 at 0, 3 at +1, 6 at +2. Top view: 4 2 1 3 6. Bottom view: 4 2 5 3 6, since 5 is deeper than 1 at hd 0. You can replace the TreeMap with a hashmap plus tracking min and max hd for O(n) instead of O(n log n).

Vertical Order Traversal (LeetCode 987) generalises this: group nodes by hd, and within a column sort by depth, then by value for ties. The tie-breaking rule is the part candidates miss.

Height, Balanced Check and Diameter

Maximum depth

depth(node) = 1 + max(depth(left), depth(right)), with depth(null) = 0. The canonical postorder function.

Balanced binary tree (LeetCode 110)

The naive version calls height at every node: O(n²) on a skewed tree. Return height and validity in one pass by using -1 as an "unbalanced" sentinel.

public boolean isBalanced(TreeNode root) { return check(root) != -1; }

private int check(TreeNode node) {
    if (node == null) return 0;
    int l = check(node.left);
    if (l == -1) return -1;                      // short-circuit
    int r = check(node.right);
    if (r == -1 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

Diameter of a binary tree (LeetCode 543)

The longest path between any two nodes may not pass through the root. For each node, the longest path that bends there has length height(left) + height(right) edges. Return the height upward; update a global with the sum.

def diameter_of_binary_tree(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return 0
        l, r = height(node.left), height(node.right)
        best = max(best, l + r)         # path bending at this node, in edges
        return 1 + max(l, r)            # what the parent can extend
    height(root)
    return best

Example tree: at node 1, left height 2 (via 2 to 4) and right height 2 (via 3 to 6), so the diameter is 4 edges: 4-2-1-3-6. Interviewers often ask "edges or nodes?"; clarify, since the node count is one more.

Binary Tree Maximum Path Sum (LeetCode 124)

This Hard is diameter with values and negatives. A path can start and end anywhere but cannot branch. Define gain(node) as the best sum of a downward path starting at node. A negative child gain is never worth taking, so clamp it to 0.

• Returned upward: node.val + max(leftGain, rightGain) (one branch only, since the parent will extend it).
• Answer candidate: node.val + leftGain + rightGain (the path bends here).

class Solution {
    private int best = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        gain(root);
        return best;
    }

    private int gain(TreeNode node) {
        if (node == null) return 0;
        int l = Math.max(gain(node.left), 0);    // drop negative branches
        int r = Math.max(gain(node.right), 0);
        best = Math.max(best, node.val + l + r);
        return node.val + Math.max(l, r);
    }
}

def max_path_sum(root):
    best = float("-inf")
    def gain(node):
        nonlocal best
        if not node:
            return 0
        l = max(gain(node.left), 0)
        r = max(gain(node.right), 0)
        best = max(best, node.val + l + r)
        return node.val + max(l, r)
    gain(root)
    return best

Dry run on [-10, 9, 20, null, null, 15, 7] (root -10, left 9, right 20 with children 15 and 7): gain(9) = 9, best 9. gain(15) = 15, gain(7) = 7. At 20: candidate 20 + 15 + 7 = 42, returns 35. At -10: candidate -10 + 9 + 35 = 34, best stays 42. Answer 42.

Path Sum Problems: Root-to-Leaf and Any Downward Path

Path Sum I and II (LeetCode 112, 113)

Top-down: pass the remaining sum down; at a leaf, check whether it is zero. For II, collect the path with backtracking (append before recursing, pop after) and copy the list when recording.

def path_sum_ii(root, target):
    res, path = [], []
    def dfs(node, remaining):
        if not node:
            return
        path.append(node.val)
        remaining -= node.val
        if not node.left and not node.right and remaining == 0:
            res.append(path[:])             # copy, or later pops will mutate it
        dfs(node.left, remaining)
        dfs(node.right, remaining)
        path.pop()                          # backtrack
    dfs(root, target)
    return res

Note the leaf check: a node with one child is not a leaf, so [1, 2] with target 1 has no valid path. Candidates frequently get that wrong by checking node is None instead.

Path Sum III: any downward path (LeetCode 437)

Count paths going downward (not necessarily from root or to a leaf) summing to target. Brute force starts a DFS from every node: O(n²) on skewed trees. The O(n) solution is prefix sums on the root-to-node path, the same idea as subarray sum equals K, with backtracking to remove the current prefix when leaving a subtree.

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0L, 1);
    return dfs(root, 0L, targetSum, prefixCount);
}

private int dfs(TreeNode node, long sum, int target, Map<Long, Integer> cnt) {
    if (node == null) return 0;
    sum += node.val;
    int paths = cnt.getOrDefault(sum - target, 0);
    cnt.merge(sum, 1, Integer::sum);
    paths += dfs(node.left, sum, target, cnt) + dfs(node.right, sum, target, cnt);
    cnt.merge(sum, -1, Integer::sum);          // backtrack: leave this path
    return paths;
}

Using long avoids overflow with large node values, which LeetCode's tests do include. The array version of this idea is explained in the hashing guide.

Other path problems

• Sum Root to Leaf Numbers (129): pass current * 10 + val down.
• Longest Univalue Path (687): diameter-style, but a child extends only if its value matches.
• Lowest Common Ancestor (236): postorder returning the found node; see LCA explained.
• All nodes at distance K (863): convert to a graph with parent pointers, then BFS.

Build, Compare and Transform Trees

Construct from preorder and inorder (LeetCode 105)

The first preorder element is the root; its position in inorder splits left and right subtrees. A hashmap from value to inorder index makes each split O(1), giving O(n) overall instead of O(n²).

def build_tree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}
    pre = iter(preorder)

    def build(lo, hi):                   # inorder range [lo, hi]
        if lo > hi:
            return None
        val = next(pre)
        node = TreeNode(val)
        mid = idx[val]
        node.left = build(lo, mid - 1)   # left first: matches preorder
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(inorder) - 1)

This requires distinct values; say so. Preorder plus postorder alone cannot uniquely determine a general binary tree (only a full one), a common theory follow-up.

Quick ones that appear as warm-ups

• Invert Binary Tree (226): swap children at every node, any traversal.
• Same Tree (100) and Symmetric Tree (101): recursive pairwise comparison; for symmetric, compare left.left with right.right and left.right with right.left.
• Subtree of Another Tree (572): same-tree check at every node, O(m·n), or serialise both and use string matching for linear time.
• Flatten Binary Tree to Linked List (114): reverse postorder (right, left, node) with a prev pointer.
• Serialize and Deserialize (297): preorder with null markers; see the full walkthrough.

Binary Tree Practice List

Binary Tree Interview Tips

1. Clarify the definitions: diameter in edges or nodes? Path must start at root or end at leaf? Values can be negative? Duplicates allowed?
2. Say the return contract out loud: "this function returns the height of the subtree, and updates the global diameter". It is the sentence that shows you understand the recursion.
3. Handle null first. The base case defines the whole recursion: height(null) = 0, gain(null) = 0.
4. Dry run on a three-node tree and a skewed tree. Skewed trees expose O(n²) mistakes and stack-depth issues.
5. Give space as O(h) and explain h ranges from log n to n. If asked about very deep trees, offer the iterative version.
6. Prefer locals or a small result object over static fields in Java; static state leaks between test cases on online judges and looks careless in interviews.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.