Binary Tree Interview Questions and Answers
Last updated 2026-11-19
Binary tree problems are the most common data-structure topic in coding rounds because a single recursive idea unlocks dozens of questions. This page works through thirteen of them in increasing difficulty, each with a short explanation, Python and Java code, complexity and the edge cases interviewers probe.
Java snippets assume the usual class TreeNode { int val; TreeNode left, right; }. Python snippets assume a TreeNode with val, left and right.
| Problems | 13, easy to hard |
|---|---|
| Languages | Python and Java |
| Core idea | Solve for a node using answers from its children |
| Prerequisites | Recursion, queues |
The pattern and when to spot it
Almost every tree question is solved by one of two shapes. The first is top-down: pass information such as a remaining sum or a valid range down to the children. The second is bottom-up: each call returns something about its subtree, such as height, and the parent combines the two answers. Spot the second shape when the question asks for a property that depends on both children, such as diameter, balance or maximum path sum.
When the question mentions levels, nearest, shortest or view from a side, think of a queue and level-order traversal instead. For a refresher on the recursion itself see recursion interview questions, and for ordering variants see tree traversal interview questions.
Mistakes that cost marks
- Treating any node with one null child as a leaf in path-sum problems.
- Counting nodes when the problem asks for edges, which gives answers off by one in diameter.
- Initialising a maximum to 0 when values can be negative.
- Forgetting that a skewed tree of 10^5 nodes can overflow the recursion stack in Java; mention an iterative version.
- Stating O(log n) space for recursion; it is O(h), which is O(n) in the worst case.
Binary Tree Interview Questions and Answers: questions with worked answers
1 Maximum depth of a binary tree
easyA tree is as deep as its deeper subtree plus one for the current node, so recurse on both children and take the larger. An empty node has depth 0. Time O(n), space O(h) for the recursion stack, where h is the height. Edge cases: empty tree, a single node, a fully skewed tree of 10^5 nodes where recursion may overflow in Java (switch to an iterative level-order count).
pythondef max_depth(root): if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right))javaint maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }2 Invert a binary tree
easySwap the left and right children at every node. Do it before or after recursing, both work, as long as every node is visited once. Time O(n), space O(h). Edge cases: null root, a node with only one child (swap still moves it to the other side).
pythondef invert(root): if root: root.left, root.right = invert(root.right), invert(root.left) return rootjavaTreeNode invert(TreeNode root) { if (root == null) return null; TreeNode l = invert(root.left), r = invert(root.right); root.left = r; root.right = l; return root; }3 Check whether two binary trees are identical
easyCompare the two roots, then recurse on both pairs of children. Two null nodes are equal, exactly one null is a mismatch, otherwise values must match and both subtrees must be identical. Time O(min(n, m)), space O(h). Edge cases: both empty, same values but different shape, one tree a prefix of the other.
pythondef same_tree(p, q): if not p and not q: return True if not p or not q or p.val != q.val: return False return same_tree(p.left, q.left) and same_tree(p.right, q.right)javaboolean sameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null || p.val != q.val) return false; return sameTree(p.left, q.left) && sameTree(p.right, q.right); }4 Is a binary tree symmetric around its centre?
easyA tree is a mirror of itself when the left subtree mirrors the right one. Write a helper that compares two nodes and crosses the children: left.left with right.right, and left.right with right.left. Time O(n), space O(h). Edge cases: null root counts as symmetric, equal values with asymmetric shape, a root with a single child.
pythondef is_symmetric(root): def mirror(a, b): if not a and not b: return True if not a or not b or a.val != b.val: return False return mirror(a.left, b.right) and mirror(a.right, b.left) return mirror(root, root)javaboolean isSymmetric(TreeNode root) { return mirror(root, root); } private boolean mirror(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null || a.val != b.val) return false; return mirror(a.left, b.right) && mirror(a.right, b.left); }5 Does a root-to-leaf path sum to a target?
easySubtract the node value from the target while walking down. At a leaf, check whether the remainder is zero. Only count leaves, not any node with a null child. Time O(n), space O(h). Edge cases: empty tree (answer false even for target 0), negative values, a node with one child where the null side must not be treated as a leaf.
pythondef has_path_sum(root, target): if not root: return False if not root.left and not root.right: return root.val == target t = target - root.val return has_path_sum(root.left, t) or has_path_sum(root.right, t)javaboolean hasPathSum(TreeNode root, int target) { if (root == null) return false; if (root.left == null && root.right == null) return root.val == target; int t = target - root.val; return hasPathSum(root.left, t) || hasPathSum(root.right, t); }6 Level-order traversal, returning a list per level
mediumUse a queue. At each round, take the current queue size as the number of nodes on this level, pop exactly that many and push their children. Time O(n), space O(w), where w is the maximum width. Edge cases: empty tree returns an empty list, skewed tree gives one node per level.
pythonfrom collections import deque def level_order(root): res = [] if not root: return res dq = deque([root]) while dq: level = [] for _ in range(len(dq)): node = dq.popleft() level.append(node.val) if node.left: dq.append(node.left) if node.right: dq.append(node.right) res.append(level) return resjavaList<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { int size = q.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode n = q.poll(); level.add(n.val); if (n.left != null) q.add(n.left); if (n.right != null) q.add(n.right); } res.add(level); } return res; }7 Diameter of a binary tree
mediumThe longest path passes through some node as its highest point, and its length is leftHeight + rightHeight at that node. Compute heights bottom-up and update a global best on the way, so one pass is enough. Time O(n), space O(h). Edge cases: single node gives 0, the best path may avoid the root entirely, count edges not nodes.
pythondef diameter(root): best = 0 def height(n): nonlocal best if not n: return 0 l, r = height(n.left), height(n.right) best = max(best, l + r) return 1 + max(l, r) height(root) return bestjavaint best; int diameter(TreeNode root) { best = 0; height(root); return best; } private int height(TreeNode n) { if (n == null) return 0; int l = height(n.left), r = height(n.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); }8 Check whether a binary tree is height-balanced
mediumA naive check recomputes height at every node and is O(n^2). Instead return the height, or -1 as a sentinel when any subtree is unbalanced, and propagate the sentinel upward. Time O(n), space O(h). Edge cases: empty tree is balanced, a left chain of three nodes is not, difference exactly 1 is allowed.
pythondef is_balanced(root): def h(n): if not n: return 0 l = h(n.left) if l < 0: return -1 r = h(n.right) if r < 0 or abs(l - r) > 1: return -1 return 1 + max(l, r) return h(root) >= 0javaboolean isBalanced(TreeNode root) { return h(root) >= 0; } private int h(TreeNode n) { if (n == null) return 0; int l = h(n.left); if (l < 0) return -1; int r = h(n.right); if (r < 0 || Math.abs(l - r) > 1) return -1; return 1 + Math.max(l, r); }9 Lowest common ancestor of two nodes
mediumRecurse: if the current node is p or q, return it. Search both sides. If both return non-null, the current node is the split point and is the answer; otherwise pass up whichever side found something. This assumes both nodes exist in the tree. Time O(n), space O(h). Edge cases: one node is the ancestor of the other (the ancestor itself is returned), p equals q, nodes missing from the tree need a separate existence check.
pythondef lca(root, p, q): if not root or root is p or root is q: return root l, r = lca(root.left, p, q), lca(root.right, p, q) return root if l and r else (l or r)javaTreeNode lca(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode l = lca(root.left, p, q), r = lca(root.right, p, q); if (l != null && r != null) return root; return l != null ? l : r; }10 Build a tree from preorder and inorder traversals
mediumThe first preorder element is the root. Its position in inorder splits the left and right subtrees; the left size tells how many preorder items belong to the left. A hash map from value to inorder index avoids rescanning. Values must be distinct. Time O(n), space O(n) for the map and recursion. Edge cases: single element, all nodes on one side, duplicates make the problem ambiguous so state the distinct-values assumption.
pythondef build_tree(preorder, inorder): idx = {v: i for i, v in enumerate(inorder)} pos = 0 def build(lo, hi): nonlocal pos if lo > hi: return None node = TreeNode(preorder[pos]); pos += 1 m = idx[node.val] node.left = build(lo, m - 1) node.right = build(m + 1, hi) return node return build(0, len(inorder) - 1)javaint pos; Map<Integer, Integer> idx = new HashMap<>(); TreeNode buildTree(int[] pre, int[] in) { for (int i = 0; i < in.length; i++) idx.put(in[i], i); pos = 0; return build(pre, 0, in.length - 1); } private TreeNode build(int[] pre, int lo, int hi) { if (lo > hi) return null; TreeNode node = new TreeNode(pre[pos++]); int m = idx.get(node.val); node.left = build(pre, lo, m - 1); node.right = build(pre, m + 1, hi); return node; }11 Right side view of a binary tree
mediumDo a level-order traversal and keep the last node of each level. A DFS that visits the right child first and records the first node seen at each depth also works. Time O(n), space O(w). Edge cases: empty tree, left-only chain (the left nodes are visible), deeper left subtree that pokes out below the right one.
pythonfrom collections import deque def right_side(root): res = [] if not root: return res dq = deque([root]) while dq: n = len(dq) for i in range(n): node = dq.popleft() if i == n - 1: res.append(node.val) if node.left: dq.append(node.left) if node.right: dq.append(node.right) return resjavaList<Integer> rightSide(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { int n = q.size(); for (int i = 0; i < n; i++) { TreeNode node = q.poll(); if (i == n - 1) res.add(node.val); if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); } } return res; }12 Maximum path sum in a binary tree
hardA path may start and end anywhere. At each node, the best downward gain is node plus the larger child gain, floored at zero so negative branches are dropped. The best path through this node as its top is node plus both clipped gains; track the global maximum. Time O(n), space O(h). Edge cases: all values negative (answer is the largest single node, so initialise best to negative infinity, not 0), single node, a path that skips the root.
pythondef max_path_sum(root): best = float('-inf') def gain(n): nonlocal best if not n: return 0 l, r = max(gain(n.left), 0), max(gain(n.right), 0) best = max(best, n.val + l + r) return n.val + max(l, r) gain(root) return bestjavaint best; int maxPathSum(TreeNode root) { best = Integer.MIN_VALUE; gain(root); return best; } private int gain(TreeNode n) { if (n == null) return 0; int l = Math.max(gain(n.left), 0), r = Math.max(gain(n.right), 0); best = Math.max(best, n.val + l + r); return n.val + Math.max(l, r); }13 Serialize and deserialize a binary tree
hardWrite preorder with a marker such as # for null, comma separated. That string is enough to rebuild the tree uniquely, because the marker fixes each node shape. Deserialise by consuming tokens in the same order with a shared iterator. Time O(n) each way, space O(n). Edge cases: empty tree gives "#", negative numbers and multi-digit values (hence a delimiter), very deep trees where recursion limits matter.
pythondef serialize(root): out = [] def go(n): if not n: out.append('#'); return out.append(str(n.val)); go(n.left); go(n.right) go(root) return ','.join(out) def deserialize(s): it = iter(s.split(',')) def go(): t = next(it) if t == '#': return None node = TreeNode(int(t)) node.left = go(); node.right = go() return node return go()javaString serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); ser(root, sb); return sb.toString(); } private 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); } int p; TreeNode deserialize(String s) { p = 0; return de(s.split(",")); } private TreeNode de(String[] t) { String x = t[p++]; if (x.equals("#")) return null; TreeNode n = new TreeNode(Integer.parseInt(x)); n.left = de(t); n.right = de(t); return n; }
Frequently asked questions
What is the difference between a binary tree and a binary search tree?
A binary tree only limits each node to two children. A binary search tree adds an ordering rule: everything in the left subtree is smaller and everything in the right is larger, which enables O(h) search.
Should I write tree solutions recursively or iteratively in an interview?
Start recursively because it is shorter and easier to get right, then mention that deep or skewed trees can overflow the stack and describe the iterative version with an explicit stack or queue.
How do I find the time complexity of a tree recursion?
Count how many times each node is visited. If every node is visited a constant number of times the cost is O(n). Space is the recursion depth, O(h).
Which tree questions come up most in coding rounds?
Maximum depth, level-order traversal, lowest common ancestor, diameter and path sum appear very often. Practise them first, then try the DSA coding round guide.
Related guides
More in DSA Interview Questions
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions