← Java Interview Prep: 8+ Years (Senior & Lead)

✓ FreeAdvanced· 14 min read

Binary Trees & BSTs — Interview Questions

Java solutions for the tree round — level-order and zigzag traversal, diameter, maximum path sum, validating a BST, the k-th smallest in a BST, serialize and deserialize, LCA in a binary tree and in a BST, flattening to a linked list, path sum I/II/III, building a tree from preorder and inorder, a sorted array to a BST, boundary, vertical, top, bottom and right-side views, symmetric and balanced checks, inorder successor, recovering a BST, counting complete-tree nodes, house robber III, a BST iterator, and merging two trees.

Published September 25, 2026

How to use this lesson

Most tree problems are either:

a DFS returning a value up the tree (height, sum, validity), often while updating a global best (diameter, maximum path sum);
or a BFS by levels (views, zigzag, level order).

For BSTs, inorder traversal is sorted; use that. The solutions use:

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

Learn it in depth → Tree Traversal

Q1. Level-order traversal, and zigzag traversal.

Short answer:

BFS with a queue, processing queue.size() nodes per level. O(n). (Level Order)
Zigzag: the same BFS, but add values to the level list at the front or back, alternating per level (using a LinkedList or Deque). (Zigzag)

List<List<Integer>> zigzag(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>(); if (root == null) return res;
    Deque<TreeNode> q = new ArrayDeque<>(List.of(root)); boolean leftToRight = true;
    while (!q.isEmpty()) {
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = q.size(); i > 0; i--) {
            TreeNode n = q.poll();
            if (leftToRight) level.addLast(n.val); else level.addFirst(n.val);
            if (n.left != null) q.add(n.left); if (n.right != null) q.add(n.right);
        }
        res.add(level); leftToRight = !leftToRight;
    }
    return res;
}

Q2. Diameter of a binary tree. Maximum path sum.

Short answer: Post-order DFS, where each call returns the best downward path from the node; the answer through a node combines its left and right values in a global.

Diameter (in edges): best = max(best, L + R), and return 1 + max(L, R). (Diameter)
Maximum path sum (the values can be negative): clamp the child gains at 0; best = max(best, node + L + R), and return node + max(L, R).

Both are O(n).

int best = Integer.MIN_VALUE;
int maxPathSum(TreeNode root) { gain(root); return best; }
int gain(TreeNode n) {
    if (n == null) return 0;
    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
    best = Math.max(best, n.val + l + r);
    return n.val + Math.max(l, r);
}

Q3. Validate a BST.

Short answer: Pass down the allowed range (low, high): the left child gets (low, node), the right child (node, high). Use long or nullable bounds to handle Integer.MIN_VALUE and MAX_VALUE. Alternatively, check that the inorder traversal is strictly increasing. O(n). (Practice)

boolean isValidBST(TreeNode n) { return valid(n, Long.MIN_VALUE, Long.MAX_VALUE); }
boolean valid(TreeNode n, long lo, long hi) {
    if (n == null) return true;
    if (n.val <= lo || n.val >= hi) return false;
    return valid(n.left, lo, n.val) && valid(n.right, n.val, hi);
}

Common trap: checking only that left.val < node.val < right.val for direct children. A deeper node can still violate an ancestor's bound.

Q4. The k-th smallest element in a BST. A BST iterator.

Short answer:

Iterative inorder traversal with an explicit stack: the k-th popped node is the answer. O(h + k). (Practice)
BST iterator: the same idea, made lazy. Keep a stack of the left spine; next() pops a node, then pushes the left spine of its right child. Amortised O(1) per call, O(h) memory.
For frequent k-th queries under updates: store the subtree sizes in the nodes (an order-statistic tree).

class BSTIterator {
    private final Deque<TreeNode> st = new ArrayDeque<>();
    BSTIterator(TreeNode root) { pushLeft(root); }
    public int next() { TreeNode n = st.pop(); pushLeft(n.right); return n.val; }
    public boolean hasNext() { return !st.isEmpty(); }
    private void pushLeft(TreeNode n) { for (; n != null; n = n.left) st.push(n); }
}
int kthSmallest(TreeNode root, int k) {
    BSTIterator it = new BSTIterator(root);
    while (--k > 0) it.next();
    return it.next();
}

Q5. Serialize and deserialize a binary tree.

Short answer: Preorder, with null markers ("1,2,#,#,3,4,#,#,5,#,#"); deserialize recursively from a token iterator. O(n) both ways. (BFS level order with nulls also works.) For a BST, preorder without nulls is enough (rebuild it with bounds).

String serialize(TreeNode n) {
    StringBuilder sb = new StringBuilder(); ser(n, sb); return sb.toString();
}
void ser(TreeNode n, StringBuilder sb) {
    if (n == null) { sb.append("#,"); return; }
    sb.append(n.val).append(','); ser(n.left, sb); ser(n.right, sb);
}
TreeNode deserialize(String data) { return des(new ArrayDeque<>(Arrays.asList(data.split(",")))); }
TreeNode des(Deque<String> t) {
    String v = t.poll();
    if (v == null || v.equals("#")) return null;
    TreeNode n = new TreeNode(Integer.parseInt(v));
    n.left = des(t); n.right = des(t);
    return n;
}

Q6. The lowest common ancestor in a binary tree, and in a BST.

Short answer:

Binary tree: recurse; if the node is p or q, return it. If both the left and right results are non-null, this node is the LCA; otherwise return whichever side is non-null. O(n). (LCA)
BST: walk down from the root: if both values are smaller, go left; if both are larger, go right; otherwise the split point is the LCA. O(h). (LCA in a BST)

TreeNode lca(TreeNode n, TreeNode p, TreeNode q) {
    if (n == null || n == p || n == q) return n;
    TreeNode l = lca(n.left, p, q), r = lca(n.right, p, q);
    return l != null && r != null ? n : (l != null ? l : r);
}
TreeNode lcaBst(TreeNode n, TreeNode p, TreeNode q) {
    while (n != null) {
        if (p.val < n.val && q.val < n.val) n = n.left;
        else if (p.val > n.val && q.val > n.val) n = n.right;
        else return n;
    }
    return null;
}

Q7. Flatten a binary tree to a linked list (in preorder).

Short answer: Morris-style, O(1) space: for each node with a left subtree, find the rightmost node of the left subtree, attach the node's right subtree there, move the left subtree to the right, and set left = null. Then continue to the right. O(n).

void flatten(TreeNode root) {
    for (TreeNode cur = root; cur != null; cur = cur.right) {
        if (cur.left == null) continue;
        TreeNode pre = cur.left;
        while (pre.right != null) pre = pre.right;
        pre.right = cur.right; cur.right = cur.left; cur.left = null;
    }
}

Q8. Path sum I, II and III.

Short answer:

I (does any root-to-leaf path sum to the target?): subtract as you go down, and check at the leaves.
II (all such paths): DFS with a path list, and backtracking. (Path Sum II)
III (count the downward paths starting anywhere): prefix sums on the current root-to-node path. count += freq[curSum - target]; add curSum to the map before recursing, and remove it afterwards. O(n), instead of O(n²).

int pathSumIII(TreeNode root, int target) {
    Map<Long, Integer> freq = new HashMap<>(Map.of(0L, 1));
    return dfs(root, 0L, target, freq);
}
int dfs(TreeNode n, long sum, int target, Map<Long, Integer> freq) {
    if (n == null) return 0;
    sum += n.val;
    int count = freq.getOrDefault(sum - target, 0);
    freq.merge(sum, 1, Integer::sum);
    count += dfs(n.left, sum, target, freq) + dfs(n.right, sum, target, freq);
    freq.merge(sum, -1, Integer::sum);                // backtrack
    return count;
}

Q9. Construct a tree from preorder and inorder traversals.

Short answer:

The first preorder value is the root.
Its position in the inorder array splits the left and right subtrees.
Use a HashMap from value to inorder index, for O(1) lookups, and a moving preorder index. O(n).

(It needs unique values.) (Practice)

int pre = 0; Map<Integer, Integer> idx = new HashMap<>();
TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
    return build(preorder, 0, inorder.length - 1);
}
TreeNode build(int[] p, int lo, int hi) {
    if (lo > hi) return null;
    TreeNode root = new TreeNode(p[pre++]);
    int mid = idx.get(root.val);
    root.left = build(p, lo, mid - 1); root.right = build(p, mid + 1, hi);
    return root;
}

Q10. Convert a sorted array to a height-balanced BST.

Short answer: Take the middle element as the root, and recurse on the left and right halves. O(n), with a height of O(log n).

TreeNode sortedArrayToBST(int[] a) { return make(a, 0, a.length - 1); }
TreeNode make(int[] a, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;
    TreeNode n = new TreeNode(a[mid]);
    n.left = make(a, lo, mid - 1); n.right = make(a, mid + 1, hi);
    return n;
}

Q11. Boundary traversal.

Short answer: Collect, anticlockwise:

the root;
the left boundary (top-down, excluding leaves);
all the leaves (left to right);
the right boundary (bottom-up, excluding leaves).

Take care not to include the root twice when it's a leaf. O(n).

List<Integer> boundary(TreeNode root) {
    List<Integer> res = new ArrayList<>(); if (root == null) return res;
    if (!isLeaf(root)) res.add(root.val);
    for (TreeNode n = root.left; n != null; n = n.left != null ? n.left : n.right) if (!isLeaf(n)) res.add(n.val);
    leaves(root, res);
    Deque<Integer> right = new ArrayDeque<>();
    for (TreeNode n = root.right; n != null; n = n.right != null ? n.right : n.left) if (!isLeaf(n)) right.push(n.val);
    res.addAll(right);
    return res;
}
boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
void leaves(TreeNode n, List<Integer> res) {
    if (n == null) return;
    if (isLeaf(n)) { res.add(n.val); return; }
    leaves(n.left, res); leaves(n.right, res);
}

Q12. Vertical order traversal. Top view and bottom view.

Short answer: Give each node a column (the root is 0; left is −1; right is +1), and a row. Use BFS.

Vertical order: group by column (a TreeMap); within a column, sort by row, then value (in the strict version).
Top view: the first node seen in each column during BFS.
Bottom view: the last node seen in each column (overwrite it).

O(n log n) with the TreeMap (or O(n), tracking the minimum and maximum columns).

List<Integer> topView(TreeNode root) {                 // bottom view: use put instead of putIfAbsent
    TreeMap<Integer, Integer> col = new TreeMap<>();
    Deque<Map.Entry<TreeNode, Integer>> q = new ArrayDeque<>();
    if (root != null) q.add(Map.entry(root, 0));
    while (!q.isEmpty()) {
        var e = q.poll(); TreeNode n = e.getKey(); int c = e.getValue();
        col.putIfAbsent(c, n.val);
        if (n.left != null) q.add(Map.entry(n.left, c - 1));
        if (n.right != null) q.add(Map.entry(n.right, c + 1));
    }
    return new ArrayList<>(col.values());
}

Q13. Right-side view.

Short answer: BFS, taking the last node of each level; or DFS visiting the right child first, and recording the first node seen at each new depth. O(n).

List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); dfs(root, 0, res); return res; }
void dfs(TreeNode n, int depth, List<Integer> res) {
    if (n == null) return;
    if (depth == res.size()) res.add(n.val);
    dfs(n.right, depth + 1, res); dfs(n.left, depth + 1, res);
}

Q14. Symmetric tree. Balanced binary tree.

Short answer:

Symmetric: compare the tree with its mirror: mirror(a, b) = a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left). O(n).
Balanced: a post-order height calculation that returns −1 as soon as any subtree is unbalanced (early exit). That makes it O(n), instead of the O(n²) of calling height() at every node.

boolean isSymmetric(TreeNode r) { return r == null || mirror(r.left, r.right); }
boolean mirror(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}
boolean isBalanced(TreeNode r) { return height(r) != -1; }
int height(TreeNode n) {
    if (n == null) return 0;
    int l = height(n.left), r = height(n.right);
    if (l == -1 || r == -1 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

Q15. The inorder successor in a BST.

Short answer: Walk from the root: if p.val < node.val, this node is a candidate, so go left; otherwise go right. O(h). (With parent pointers: it's the leftmost node of the right subtree, if there is one; otherwise go up until you arrive from a left child.)

TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode succ = null;
    while (root != null) {
        if (p.val < root.val) { succ = root; root = root.left; } else root = root.right;
    }
    return succ;
}

Q16. Recover a BST (two nodes were swapped).

Short answer: In an inorder traversal, find the inversions, where prev.val > cur.val:

the first node of the first inversion is one swapped node;
the second node of the last inversion is the other.

Swap their values back. O(n) time; O(h) space with recursion (O(1) with Morris traversal).

TreeNode first, second, prev;
void recoverTree(TreeNode root) { inorder(root); int t = first.val; first.val = second.val; second.val = t; }
void inorder(TreeNode n) {
    if (n == null) return;
    inorder(n.left);
    if (prev != null && prev.val > n.val) { if (first == null) first = prev; second = n; }
    prev = n;
    inorder(n.right);
}

Q17. Count the nodes of a complete tree (faster than O(n)).

Short answer: Compare the leftmost depth and the rightmost depth. If they're equal, the subtree is perfect: 2^h − 1 nodes. Otherwise, recurse on both children. That's O(log² n).

int countNodes(TreeNode n) {
    if (n == null) return 0;
    int lh = 0, rh = 0;
    for (TreeNode t = n; t != null; t = t.left) lh++;
    for (TreeNode t = n; t != null; t = t.right) rh++;
    if (lh == rh) return (1 << lh) - 1;
    return 1 + countNodes(n.left) + countNodes(n.right);
}

Q18. House robber III (on a tree).

Short answer: This is tree DP. Each node returns a pair: {best if robbed, best if not robbed}.

If robbed: val + notRobbed(left) + notRobbed(right).
If not robbed: max(left) + max(right).

O(n).

int rob(TreeNode root) { int[] r = robPair(root); return Math.max(r[0], r[1]); }
int[] robPair(TreeNode n) {                      // {robbed, notRobbed}
    if (n == null) return new int[2];
    int[] l = robPair(n.left), r = robPair(n.right);
    return new int[]{n.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])};
}

Q19. Merge two binary trees.

Short answer: Recurse on both trees together: if one node is null, return the other; otherwise add the values, and merge the children. O(min(n₁, n₂)) (this reuses the nodes of tree 1).

TreeNode mergeTrees(TreeNode a, TreeNode b) {
    if (a == null) return b; if (b == null) return a;
    a.val += b.val;
    a.left = mergeTrees(a.left, b.left); a.right = mergeTrees(a.right, b.right);
    return a;
}

Follow-up questions this topic invites — and their answers

Q: Recursion or iteration for tree traversal? A: Recursion is clearer, but it uses O(h) stack; a degenerate (linked-list-like) tree with 100,000 nodes can overflow it. Iterative traversal with an explicit Deque, or Morris traversal (O(1) space, temporarily modifying pointers), avoids that.

Q: What's the time complexity of BST operations? A: O(h): O(log n) when balanced, O(n) when skewed. Java's TreeMap is a red-black tree, so it guarantees O(log n).

Q: Why use a global variable (or a holder) in the diameter and max-path problems? A: The value returned to the parent (the best single downward path) differs from the answer through the node (both sides combined), so the best combination is tracked separately.

Q: How do you check whether a tree is complete? A: BFS: once you see a null child, no non-null node may appear afterwards in the level order.

Stacks, Queues & Monotonic Stacks — Interview Questions

Graph Algorithms — Interview Questions

← Java Interview Prep: 8+ Years (Senior & Lead)

✓ FreeAdvanced· 14 min read

Binary Trees & BSTs — Interview Questions

Published September 25, 2026

How to use this lesson

Most tree problems are either:

a DFS returning a value up the tree (height, sum, validity), often while updating a global best (diameter, maximum path sum);
or a BFS by levels (views, zigzag, level order).

For BSTs, inorder traversal is sorted; use that. The solutions use:

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

Learn it in depth → Tree Traversal

Q1. Level-order traversal, and zigzag traversal.

Short answer:

BFS with a queue, processing queue.size() nodes per level. O(n). (Level Order)
Zigzag: the same BFS, but add values to the level list at the front or back, alternating per level (using a LinkedList or Deque). (Zigzag)

List<List<Integer>> zigzag(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>(); if (root == null) return res;
    Deque<TreeNode> q = new ArrayDeque<>(List.of(root)); boolean leftToRight = true;
    while (!q.isEmpty()) {
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = q.size(); i > 0; i--) {
            TreeNode n = q.poll();
            if (leftToRight) level.addLast(n.val); else level.addFirst(n.val);
            if (n.left != null) q.add(n.left); if (n.right != null) q.add(n.right);
        }
        res.add(level); leftToRight = !leftToRight;
    }
    return res;
}

Q2. Diameter of a binary tree. Maximum path sum.

Short answer: Post-order DFS, where each call returns the best downward path from the node; the answer through a node combines its left and right values in a global.

Diameter (in edges): best = max(best, L + R), and return 1 + max(L, R). (Diameter)
Maximum path sum (the values can be negative): clamp the child gains at 0; best = max(best, node + L + R), and return node + max(L, R).

Both are O(n).

int best = Integer.MIN_VALUE;
int maxPathSum(TreeNode root) { gain(root); return best; }
int gain(TreeNode n) {
    if (n == null) return 0;
    int l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
    best = Math.max(best, n.val + l + r);
    return n.val + Math.max(l, r);
}

Q3. Validate a BST.

boolean isValidBST(TreeNode n) { return valid(n, Long.MIN_VALUE, Long.MAX_VALUE); }
boolean valid(TreeNode n, long lo, long hi) {
    if (n == null) return true;
    if (n.val <= lo || n.val >= hi) return false;
    return valid(n.left, lo, n.val) && valid(n.right, n.val, hi);
}

Common trap: checking only that left.val < node.val < right.val for direct children. A deeper node can still violate an ancestor's bound.

Q4. The k-th smallest element in a BST. A BST iterator.

Short answer:

Iterative inorder traversal with an explicit stack: the k-th popped node is the answer. O(h + k). (Practice)
BST iterator: the same idea, made lazy. Keep a stack of the left spine; next() pops a node, then pushes the left spine of its right child. Amortised O(1) per call, O(h) memory.
For frequent k-th queries under updates: store the subtree sizes in the nodes (an order-statistic tree).

class BSTIterator {
    private final Deque<TreeNode> st = new ArrayDeque<>();
    BSTIterator(TreeNode root) { pushLeft(root); }
    public int next() { TreeNode n = st.pop(); pushLeft(n.right); return n.val; }
    public boolean hasNext() { return !st.isEmpty(); }
    private void pushLeft(TreeNode n) { for (; n != null; n = n.left) st.push(n); }
}
int kthSmallest(TreeNode root, int k) {
    BSTIterator it = new BSTIterator(root);
    while (--k > 0) it.next();
    return it.next();
}

Q5. Serialize and deserialize a binary tree.

String serialize(TreeNode n) {
    StringBuilder sb = new StringBuilder(); ser(n, sb); return sb.toString();
}
void ser(TreeNode n, StringBuilder sb) {
    if (n == null) { sb.append("#,"); return; }
    sb.append(n.val).append(','); ser(n.left, sb); ser(n.right, sb);
}
TreeNode deserialize(String data) { return des(new ArrayDeque<>(Arrays.asList(data.split(",")))); }
TreeNode des(Deque<String> t) {
    String v = t.poll();
    if (v == null || v.equals("#")) return null;
    TreeNode n = new TreeNode(Integer.parseInt(v));
    n.left = des(t); n.right = des(t);
    return n;
}

Q6. The lowest common ancestor in a binary tree, and in a BST.

Short answer:

Binary tree: recurse; if the node is p or q, return it. If both the left and right results are non-null, this node is the LCA; otherwise return whichever side is non-null. O(n). (LCA)
BST: walk down from the root: if both values are smaller, go left; if both are larger, go right; otherwise the split point is the LCA. O(h). (LCA in a BST)

TreeNode lca(TreeNode n, TreeNode p, TreeNode q) {
    if (n == null || n == p || n == q) return n;
    TreeNode l = lca(n.left, p, q), r = lca(n.right, p, q);
    return l != null && r != null ? n : (l != null ? l : r);
}
TreeNode lcaBst(TreeNode n, TreeNode p, TreeNode q) {
    while (n != null) {
        if (p.val < n.val && q.val < n.val) n = n.left;
        else if (p.val > n.val && q.val > n.val) n = n.right;
        else return n;
    }
    return null;
}

Q7. Flatten a binary tree to a linked list (in preorder).

void flatten(TreeNode root) {
    for (TreeNode cur = root; cur != null; cur = cur.right) {
        if (cur.left == null) continue;
        TreeNode pre = cur.left;
        while (pre.right != null) pre = pre.right;
        pre.right = cur.right; cur.right = cur.left; cur.left = null;
    }
}

Q8. Path sum I, II and III.

Short answer:

I (does any root-to-leaf path sum to the target?): subtract as you go down, and check at the leaves.
II (all such paths): DFS with a path list, and backtracking. (Path Sum II)
III (count the downward paths starting anywhere): prefix sums on the current root-to-node path. count += freq[curSum - target]; add curSum to the map before recursing, and remove it afterwards. O(n), instead of O(n²).

int pathSumIII(TreeNode root, int target) {
    Map<Long, Integer> freq = new HashMap<>(Map.of(0L, 1));
    return dfs(root, 0L, target, freq);
}
int dfs(TreeNode n, long sum, int target, Map<Long, Integer> freq) {
    if (n == null) return 0;
    sum += n.val;
    int count = freq.getOrDefault(sum - target, 0);
    freq.merge(sum, 1, Integer::sum);
    count += dfs(n.left, sum, target, freq) + dfs(n.right, sum, target, freq);
    freq.merge(sum, -1, Integer::sum);                // backtrack
    return count;
}

Q9. Construct a tree from preorder and inorder traversals.

Short answer:

The first preorder value is the root.
Its position in the inorder array splits the left and right subtrees.
Use a HashMap from value to inorder index, for O(1) lookups, and a moving preorder index. O(n).

(It needs unique values.) (Practice)

int pre = 0; Map<Integer, Integer> idx = new HashMap<>();
TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
    return build(preorder, 0, inorder.length - 1);
}
TreeNode build(int[] p, int lo, int hi) {
    if (lo > hi) return null;
    TreeNode root = new TreeNode(p[pre++]);
    int mid = idx.get(root.val);
    root.left = build(p, lo, mid - 1); root.right = build(p, mid + 1, hi);
    return root;
}

Q10. Convert a sorted array to a height-balanced BST.

Short answer: Take the middle element as the root, and recurse on the left and right halves. O(n), with a height of O(log n).

TreeNode sortedArrayToBST(int[] a) { return make(a, 0, a.length - 1); }
TreeNode make(int[] a, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;
    TreeNode n = new TreeNode(a[mid]);
    n.left = make(a, lo, mid - 1); n.right = make(a, mid + 1, hi);
    return n;
}

Q11. Boundary traversal.

Short answer: Collect, anticlockwise:

the root;
the left boundary (top-down, excluding leaves);
all the leaves (left to right);
the right boundary (bottom-up, excluding leaves).

Take care not to include the root twice when it's a leaf. O(n).

List<Integer> boundary(TreeNode root) {
    List<Integer> res = new ArrayList<>(); if (root == null) return res;
    if (!isLeaf(root)) res.add(root.val);
    for (TreeNode n = root.left; n != null; n = n.left != null ? n.left : n.right) if (!isLeaf(n)) res.add(n.val);
    leaves(root, res);
    Deque<Integer> right = new ArrayDeque<>();
    for (TreeNode n = root.right; n != null; n = n.right != null ? n.right : n.left) if (!isLeaf(n)) right.push(n.val);
    res.addAll(right);
    return res;
}
boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
void leaves(TreeNode n, List<Integer> res) {
    if (n == null) return;
    if (isLeaf(n)) { res.add(n.val); return; }
    leaves(n.left, res); leaves(n.right, res);
}

Q12. Vertical order traversal. Top view and bottom view.

Short answer: Give each node a column (the root is 0; left is −1; right is +1), and a row. Use BFS.

Vertical order: group by column (a TreeMap); within a column, sort by row, then value (in the strict version).
Top view: the first node seen in each column during BFS.
Bottom view: the last node seen in each column (overwrite it).

O(n log n) with the TreeMap (or O(n), tracking the minimum and maximum columns).

List<Integer> topView(TreeNode root) {                 // bottom view: use put instead of putIfAbsent
    TreeMap<Integer, Integer> col = new TreeMap<>();
    Deque<Map.Entry<TreeNode, Integer>> q = new ArrayDeque<>();
    if (root != null) q.add(Map.entry(root, 0));
    while (!q.isEmpty()) {
        var e = q.poll(); TreeNode n = e.getKey(); int c = e.getValue();
        col.putIfAbsent(c, n.val);
        if (n.left != null) q.add(Map.entry(n.left, c - 1));
        if (n.right != null) q.add(Map.entry(n.right, c + 1));
    }
    return new ArrayList<>(col.values());
}

Q13. Right-side view.

Short answer: BFS, taking the last node of each level; or DFS visiting the right child first, and recording the first node seen at each new depth. O(n).

List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); dfs(root, 0, res); return res; }
void dfs(TreeNode n, int depth, List<Integer> res) {
    if (n == null) return;
    if (depth == res.size()) res.add(n.val);
    dfs(n.right, depth + 1, res); dfs(n.left, depth + 1, res);
}

Q14. Symmetric tree. Balanced binary tree.

Short answer:

Symmetric: compare the tree with its mirror: mirror(a, b) = a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left). O(n).
Balanced: a post-order height calculation that returns −1 as soon as any subtree is unbalanced (early exit). That makes it O(n), instead of the O(n²) of calling height() at every node.

boolean isSymmetric(TreeNode r) { return r == null || mirror(r.left, r.right); }
boolean mirror(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}
boolean isBalanced(TreeNode r) { return height(r) != -1; }
int height(TreeNode n) {
    if (n == null) return 0;
    int l = height(n.left), r = height(n.right);
    if (l == -1 || r == -1 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

Q15. The inorder successor in a BST.

TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode succ = null;
    while (root != null) {
        if (p.val < root.val) { succ = root; root = root.left; } else root = root.right;
    }
    return succ;
}

Q16. Recover a BST (two nodes were swapped).

Short answer: In an inorder traversal, find the inversions, where prev.val > cur.val:

the first node of the first inversion is one swapped node;
the second node of the last inversion is the other.

Swap their values back. O(n) time; O(h) space with recursion (O(1) with Morris traversal).

TreeNode first, second, prev;
void recoverTree(TreeNode root) { inorder(root); int t = first.val; first.val = second.val; second.val = t; }
void inorder(TreeNode n) {
    if (n == null) return;
    inorder(n.left);
    if (prev != null && prev.val > n.val) { if (first == null) first = prev; second = n; }
    prev = n;
    inorder(n.right);
}

Q17. Count the nodes of a complete tree (faster than O(n)).

int countNodes(TreeNode n) {
    if (n == null) return 0;
    int lh = 0, rh = 0;
    for (TreeNode t = n; t != null; t = t.left) lh++;
    for (TreeNode t = n; t != null; t = t.right) rh++;
    if (lh == rh) return (1 << lh) - 1;
    return 1 + countNodes(n.left) + countNodes(n.right);
}

Q18. House robber III (on a tree).

Short answer: This is tree DP. Each node returns a pair: {best if robbed, best if not robbed}.

If robbed: val + notRobbed(left) + notRobbed(right).
If not robbed: max(left) + max(right).

O(n).

int rob(TreeNode root) { int[] r = robPair(root); return Math.max(r[0], r[1]); }
int[] robPair(TreeNode n) {                      // {robbed, notRobbed}
    if (n == null) return new int[2];
    int[] l = robPair(n.left), r = robPair(n.right);
    return new int[]{n.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])};
}

Q19. Merge two binary trees.

Short answer: Recurse on both trees together: if one node is null, return the other; otherwise add the values, and merge the children. O(min(n₁, n₂)) (this reuses the nodes of tree 1).

TreeNode mergeTrees(TreeNode a, TreeNode b) {
    if (a == null) return b; if (b == null) return a;
    a.val += b.val;
    a.left = mergeTrees(a.left, b.left); a.right = mergeTrees(a.right, b.right);
    return a;
}

Follow-up questions this topic invites — and their answers

Q: What's the time complexity of BST operations? A: O(h): O(log n) when balanced, O(n) when skewed. Java's TreeMap is a red-black tree, so it guarantees O(log n).

Q: How do you check whether a tree is complete? A: BFS: once you see a null child, no non-null node may appear afterwards in the level order.

Stacks, Queues & Monotonic Stacks — Interview Questions

Graph Algorithms — Interview Questions