🎯 JavaScript Trees — Top 25 Interview Questions
Q1 — Maximum Depth of Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Height = 1 + max(left, right); base case null → 0.
Step 2 — Brute force (what NOT to do): BFS counting levels — works but more code.
Step 3 — Optimal insight: Single DFS recursion; return value bubbles up the max depth.
Step 4 — Algorithm:
1. If node null → return 0
2. Recurse left and right
3. Return 1 + Math.max(left, right)
Step 5 — Edge cases: Empty tree → 0; single node → 1.
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}Time: O(n) | Space: O(h)
Q2 — Invert Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Swap left/right children at every node recursively.
Step 2 — Brute force (what NOT to do): Rebuild the tree — wasteful.
Step 3 — Optimal insight: Swap in-place then recurse.
Step 4 — Algorithm:
1. If null → return null
2. Swap left and right
3. Recurse on both
Step 5 — Edge cases: Null root; single node.
function invertTree(root) {
if (!root) return null;
[root.left, root.right] = [root.right, root.left];
invertTree(root.left);
invertTree(root.right);
return root;
}Time: O(n) | Space: O(h)
Q3 — Symmetric Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Mirror check — l.left mirrors r.right, l.right mirrors r.left.
Step 2 — Brute force (what NOT to do): Inorder palindrome check — fails for some cases.
Step 3 — Optimal insight: Recursive helper comparing two subtrees.
Step 4 — Algorithm:
1. isMirror(l, r): both null → true; one null → false
2. vals equal AND isMirror(l.left, r.right) AND isMirror(l.right, r.left)
Step 5 — Edge cases: Single node → true.
function isSymmetric(root) {
return isMirror(root?.left, root?.right);
}
function isMirror(l, r) {
if (!l && !r) return true;
if (!l || !r) return false;
return l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left);
}Time: O(n) | Space: O(h)
Q4 — Path Sum
🧠 How to Approach This
Step 1 — Recognize the pattern: Subtract node value at each step; check leaf when remainder = 0.
Step 2 — Brute force (what NOT to do): Enumerate all paths then sum — extra space.
Step 3 — Optimal insight: Pass remaining target down; at leaf check rem === 0.
Step 4 — Algorithm:
1. If null → false
2. rem = targetSum - root.val
3. If leaf and rem === 0 → true
4. return hasPathSum(left, rem) || hasPathSum(right, rem)
Step 5 — Edge cases: Negative values allowed.
function hasPathSum(root, targetSum) {
if (!root) return false;
const rem = targetSum - root.val;
if (!root.left && !root.right) return rem === 0;
return hasPathSum(root.left, rem) || hasPathSum(root.right, rem);
}Time: O(n) | Space: O(h)
Q5 — Level Order Traversal
🧠 How to Approach This
Step 1 — Recognize the pattern: BFS with level-size tracking.
Step 2 — Brute force (what NOT to do): DFS with level markers — more complex.
Step 3 — Optimal insight: Process queue in batches of current level size.
Step 4 — Algorithm:
1. Init queue with root
2. While queue: capture size, process that many nodes, enqueue children
Step 5 — Edge cases: Empty tree → [].
function levelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const size = queue.length, level = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}Time: O(n) | Space: O(w)
Q6 — Validate Binary Search Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Every node must be within (min, max) bounds.
Step 2 — Brute force (what NOT to do): Inorder check only — insufficient.
Step 3 — Optimal insight: Pass min/max bounds; tighten at each step.
Step 4 — Algorithm:
1. validate(node, min=-Inf, max=+Inf)
2. If val ≤ min or val ≥ max → false
3. Recurse left with max=val, right with min=val
Step 5 — Edge cases: Integer boundary values.
function isValidBST(root, min = -Infinity, max = Infinity) {
if (!root) return true;
if (root.val <= min || root.val >= max) return false;
return isValidBST(root.left, min, root.val)
&& isValidBST(root.right, root.val, max);
}Time: O(n) | Space: O(h)
Q7 — Lowest Common Ancestor of BST
🧠 How to Approach This
Step 1 — Recognize the pattern: BST property narrows direction at each step.
Step 2 — Brute force (what NOT to do): General LCA ignoring BST property — O(n).
Step 3 — Optimal insight: Both < root → go left; both > root → go right; else root is LCA.
Step 4 — Algorithm:
1. If both p,q < root.val → recurse left
2. If both > root.val → recurse right
3. Else return root
Step 5 — Edge cases: p or q equals root.
function lowestCommonAncestor(root, p, q) {
if (p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);
if (p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);
return root;
}Time: O(h) | Space: O(h)
Q8 — Lowest Common Ancestor of Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Post-order DFS; both sides non-null → current node is LCA.
Step 2 — Brute force (what NOT to do): Store root-to-node paths then compare.
Step 3 — Optimal insight: Single DFS returning node when found.
Step 4 — Algorithm:
1. If null or matches p/q → return node
2. Both sides non-null → return root
3. Else return whichever is non-null
Step 5 — Edge cases: p is ancestor of q.
function lcaBinaryTree(root, p, q) {
if (!root || root === p || root === q) return root;
const left = lcaBinaryTree(root.left, p, q);
const right = lcaBinaryTree(root.right, p, q);
return left && right ? root : (left || right);
}Time: O(n) | Space: O(h)
Q9 — Binary Tree Right Side View
🧠 How to Approach This
Step 1 — Recognize the pattern: BFS — take last node at each level.
Step 2 — Brute force (what NOT to do): DFS with level tracking — more complex.
Step 3 — Optimal insight: During BFS record the last node per level.
Step 4 — Algorithm:
1. BFS level-order
2. At i === size-1 → push to result
Step 5 — Edge cases: Left-skewed tree.
function rightSideView(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (i === size - 1) result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
}Time: O(n) | Space: O(w)
Q10 — Count Good Nodes in Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Track max on path; node is good if val >= max.
Step 2 — Brute force (what NOT to do): Store entire path array — extra space.
Step 3 — Optimal insight: Pass running max down; count at each good node.
Step 4 — Algorithm:
1. dfs(node, maxSoFar)
2. good = node.val >= maxSoFar ? 1 : 0
3. Recurse both children with updated max
Step 5 — Edge cases: Root is always good.
function goodNodes(root) {
function dfs(node, maxVal) {
if (!node) return 0;
const good = node.val >= maxVal ? 1 : 0;
const newMax = Math.max(maxVal, node.val);
return good + dfs(node.left, newMax) + dfs(node.right, newMax);
}
return dfs(root, -Infinity);
}Time: O(n) | Space: O(h)
Q11 — Kth Smallest in BST
🧠 How to Approach This
Step 1 — Recognize the pattern: Inorder of BST = sorted; stop at kth element.
Step 2 — Brute force (what NOT to do): Collect all values then index — O(n) space.
Step 3 — Optimal insight: Iterative inorder with early exit.
Step 4 — Algorithm:
1. Iterative inorder with stack
2. Decrement k on each pop; return when k === 0
Step 5 — Edge cases: k=1 (minimum); k=n (maximum).
function kthSmallest(root, k) {
const stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) { stack.push(curr); curr = curr.left; }
curr = stack.pop();
if (--k === 0) return curr.val;
curr = curr.right;
}
return -1;
}Time: O(h + k) | Space: O(h)
Q12 — Binary Tree Maximum Path Sum
🧠 How to Approach This
Step 1 — Recognize the pattern: At each node, path through it = node + max(0,left) + max(0,right).
Step 2 — Brute force (what NOT to do): Try all node pairs — O(n²).
Step 3 — Optimal insight: Post-order; track global max; return only one branch to parent.
Step 4 — Algorithm:
1. gain(node) = node.val + max(0, gain(left)) + max(0, gain(right)) → update max
2. Return node.val + max(0, max(gainL, gainR))
Step 5 — Edge cases: All negative values; single node.
function maxPathSum(root) {
let max = -Infinity;
function gain(node) {
if (!node) return 0;
const l = Math.max(0, gain(node.left));
const r = Math.max(0, gain(node.right));
max = Math.max(max, node.val + l + r);
return node.val + Math.max(l, r);
}
gain(root);
return max;
}Time: O(n) | Space: O(h)
Q13 — Serialize and Deserialize Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Preorder DFS + null markers.
Step 2 — Brute force (what NOT to do): Level-order with position indices — complex.
Step 3 — Optimal insight: "val,#,#" format is self-describing; recurse on token list.
Step 4 — Algorithm:
1. Serialize: DFS preorder, "#" for null, join with ","
2. Deserialize: split, index pointer, recurse
Step 5 — Edge cases: Empty tree → "#"; single node → "1,#,#".
function serialize(root) {
if (!root) return '#';
return root.val + ',' + serialize(root.left) + ',' + serialize(root.right);
}
function deserialize(data) {
const tokens = data.split(',');
let idx = 0;
function build() {
const val = tokens[idx++];
if (val === '#') return null;
const node = new TreeNode(+val);
node.left = build();
node.right = build();
return node;
}
return build();
}Time: O(n) | Space: O(n)
Q14 — Construct Tree from Preorder + Inorder
🧠 How to Approach This
Step 1 — Recognize the pattern: preorder[0] is root; find in inorder to split subtrees.
Step 2 — Brute force (what NOT to do): Linear scan inorder at each level — O(n²).
Step 3 — Optimal insight: Map inorder indices for O(1) lookup.
Step 4 — Algorithm:
1. Build index map from inorder
2. build(preL, preR, inL, inR): preorder[preL] is root
3. leftSize = rootIdx - inL; recurse
Step 5 — Edge cases: Single element arrays.
function buildTree(preorder, inorder) {
const map = new Map(inorder.map((v, i) => [v, i]));
function build(preL, preR, inL, inR) {
if (preL > preR) return null;
const rootVal = preorder[preL];
const node = new TreeNode(rootVal);
const rootIdx = map.get(rootVal);
const leftSize = rootIdx - inL;
node.left = build(preL + 1, preL + leftSize, inL, rootIdx - 1);
node.right = build(preL + leftSize + 1, preR, rootIdx + 1, inR);
return node;
}
return build(0, preorder.length - 1, 0, inorder.length - 1);
}Time: O(n) | Space: O(n)
Q15 — Flatten Binary Tree to Linked List
🧠 How to Approach This
Step 1 — Recognize the pattern: Preorder order; rewire right pointers, left = null.
Step 2 — Brute force (what NOT to do): Collect preorder in array, rewire — O(n) space.
Step 3 — Optimal insight: Find rightmost of left subtree, attach right there, move left to right.
Step 4 — Algorithm:
1. While curr: if left, find rightmost of left → attach curr.right
2. curr.right = curr.left; curr.left = null; advance
Step 5 — Edge cases: No left child.
function flatten(root) {
let curr = root;
while (curr) {
if (curr.left) {
let prev = curr.left;
while (prev.right) prev = prev.right;
prev.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
curr = curr.right;
}
}Time: O(n) | Space: O(1)
Q16 — Diameter of Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Diameter through node = height(left) + height(right).
Step 2 — Brute force (what NOT to do): Compute height per node separately — O(n²).
Step 3 — Optimal insight: Combine height + diameter in one DFS.
Step 4 — Algorithm:
1. DFS returns height; update max with l+r
2. Return 1 + max(l, r) to parent
Step 5 — Edge cases: Path need not pass through root.
function diameterOfBinaryTree(root) {
let max = 0;
function depth(node) {
if (!node) return 0;
const l = depth(node.left);
const r = depth(node.right);
max = Math.max(max, l + r);
return 1 + Math.max(l, r);
}
depth(root);
return max;
}Time: O(n) | Space: O(h)
Q17 — Balanced Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Return -1 as sentinel for unbalanced; otherwise height.
Step 2 — Brute force (what NOT to do): Compute height separately — O(n²).
Step 3 — Optimal insight: Post-order DFS propagating -1 immediately.
Step 4 — Algorithm:
1. check(null) → 0
2. l=-1 → return -1; r=-1 → return -1
3. |l-r|>1 → return -1; else 1+max(l,r)
Step 5 — Edge cases: Empty tree → true.
function isBalanced(root) {
function check(node) {
if (!node) return 0;
const l = check(node.left); if (l === -1) return -1;
const r = check(node.right); if (r === -1) return -1;
if (Math.abs(l - r) > 1) return -1;
return 1 + Math.max(l, r);
}
return check(root) !== -1;
}Time: O(n) | Space: O(h)
Q18 — Sum Root to Leaf Numbers
🧠 How to Approach This
Step 1 — Recognize the pattern: Pass accumulated number down; add at leaf.
Step 2 — Brute force (what NOT to do): Store all paths as strings, parse.
Step 3 — Optimal insight: curr = prev * 10 + node.val; sum at leaf.
Step 4 — Algorithm:
1. dfs(node, curr=0): curr = curr*10 + val
2. If leaf → return curr
3. Return dfs(left, curr) + dfs(right, curr)
Step 5 — Edge cases: Single node → its value.
function sumNumbers(root) {
function dfs(node, curr) {
if (!node) return 0;
curr = curr * 10 + node.val;
if (!node.left && !node.right) return curr;
return dfs(node.left, curr) + dfs(node.right, curr);
}
return dfs(root, 0);
}Time: O(n) | Space: O(h)
Q19 — Path Sum II (All Paths)
🧠 How to Approach This
Step 1 — Recognize the pattern: Backtracking DFS — push, recurse, pop.
Step 2 — Brute force (what NOT to do): Copy array at each node — O(n·h) space.
Step 3 — Optimal insight: Mutate single path array; push before recurse, pop after.
Step 4 — Algorithm:
1. dfs(node, rem, path, result)
2. Push val; if leaf and rem==0 → push copy
3. Recurse left/right; pop path
Step 5 — Edge cases: No valid paths → [].
function pathSum(root, targetSum) {
const result = [];
function dfs(node, rem, path) {
if (!node) return;
path.push(node.val);
rem -= node.val;
if (!node.left && !node.right && rem === 0) result.push([...path]);
dfs(node.left, rem, path);
dfs(node.right, rem, path);
path.pop();
}
dfs(root, targetSum, []);
return result;
}Time: O(n·h) | Space: O(n·h)
Q20 — Convert Sorted Array to BST
🧠 How to Approach This
Step 1 — Recognize the pattern: Mid element = root → balanced; recurse on halves.
Step 2 — Brute force (what NOT to do): Insert one-by-one — O(n log n), may be unbalanced.
Step 3 — Optimal insight: Divide-and-conquer with mid = (l+r) >> 1.
Step 4 — Algorithm:
1. build(l, r): if l > r return null
2. mid = (l+r)>>1; node
3. left = build(l, mid-1); right = build(mid+1, r)
Step 5 — Edge cases: Empty array → null.
function sortedArrayToBST(nums) {
function build(l, r) {
if (l > r) return null;
const mid = (l + r) >> 1;
const node = new TreeNode(nums[mid]);
node.left = build(l, mid - 1);
node.right = build(mid + 1, r);
return node;
}
return build(0, nums.length - 1);
}Time: O(n) | Space: O(log n)
Q21 — Binary Tree Zigzag Level Order
🧠 How to Approach This
Step 1 — Recognize the pattern: BFS + alternate direction each level.
Step 2 — Brute force (what NOT to do): Two separate queues — complex.
Step 3 — Optimal insight: BFS + toggle + reverse on odd levels.
Step 4 — Algorithm:
1. Standard BFS with level batches
2. Toggle ltr; if !ltr → level.reverse()
Step 5 — Edge cases: Single node.
function zigzagLevelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
let ltr = true;
while (queue.length) {
const size = queue.length, level = [];
for (let i = 0; i < size; i++) {
const n = queue.shift();
level.push(n.val);
if (n.left) queue.push(n.left);
if (n.right) queue.push(n.right);
}
result.push(ltr ? level : level.reverse());
ltr = !ltr;
}
return result;
}Time: O(n) | Space: O(w)
Q22 — Delete Node in BST
🧠 How to Approach This
Step 1 — Recognize the pattern: Three cases: leaf, one child, two children (inorder successor).
Step 2 — Brute force (what NOT to do): Rebuild BST — O(n).
Step 3 — Optimal insight: Replace value with inorder successor, delete successor.
Step 4 — Algorithm:
1. Recurse to find key
2. Leaf → null; one child → return it
3. Two children: find min of right subtree, replace val, delete that node
Step 5 — Edge cases: Key not present; root deletion.
function deleteNode(root, key) {
if (!root) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else {
if (!root.left) return root.right;
if (!root.right) return root.left;
let succ = root.right;
while (succ.left) succ = succ.left;
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
}Time: O(h) | Space: O(h)
Q23 — Binary Tree Level Order Bottom-Up
🧠 How to Approach This
Step 1 — Recognize the pattern: Standard BFS level-order then reverse.
Step 2 — Brute force (what NOT to do): DFS with depth tracking and sort.
Step 3 — Optimal insight: BFS + result.reverse() at end.
Step 4 — Algorithm:
1. Standard BFS into result
2. Return result.reverse()
Step 5 — Edge cases: Empty tree → [].
function levelOrderBottom(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const size = queue.length, level = [];
for (let i = 0; i < size; i++) {
const n = queue.shift();
level.push(n.val);
if (n.left) queue.push(n.left);
if (n.right) queue.push(n.right);
}
result.push(level);
}
return result.reverse();
}Time: O(n) | Space: O(w)
Q24 — Recover Binary Search Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: Inorder traversal finds two out-of-order nodes.
Step 2 — Brute force (what NOT to do): Collect + sort + reinsert — O(n log n).
Step 3 — Optimal insight: Track prev in inorder; first inversion → first bad; second → second bad; swap vals.
Step 4 — Algorithm:
1. Inorder DFS tracking prev
2. First violation: first = prev, second = curr
3. Second violation: second = curr only
4. Swap first.val ↔ second.val
Step 5 — Edge cases: Adjacent nodes swapped.
function recoverTree(root) {
let first = null, second = null, prev = null;
function inorder(node) {
if (!node) return;
inorder(node.left);
if (prev && prev.val > node.val) {
if (!first) first = prev;
second = node;
}
prev = node;
inorder(node.right);
}
inorder(root);
[first.val, second.val] = [second.val, first.val];
}Time: O(n) | Space: O(h)
Q25 — Maximum Width of Binary Tree
🧠 How to Approach This
Step 1 — Recognize the pattern: BFS with heap-style position indices; width = rightmost - leftmost + 1.
Step 2 — Brute force (what NOT to do): Track null nodes in queue — exponential space.
Step 3 — Optimal insight: Normalize each level's index to prevent overflow.
Step 4 — Algorithm:
1. BFS queue of [node, index] pairs
2. Per level: width = last.idx − first.idx + 1; normalize by subtracting first.idx
Step 5 — Edge cases: Single node per level → 1.
function widthOfBinaryTree(root) {
if (!root) return 0;
let maxWidth = 0;
let queue = [[root, 0]];
while (queue.length) {
const size = queue.length;
const offset = queue[0][1];
let first = 0, last = 0;
const next = [];
for (let i = 0; i < size; i++) {
const [node, idx] = queue[i];
const cur = idx - offset;
if (i === 0) first = cur;
if (i === size-1) last = cur;
if (node.left) next.push([node.left, 2 * cur]);
if (node.right) next.push([node.right, 2 * cur + 1]);
}
maxWidth = Math.max(maxWidth, last - first + 1);
queue = next;
}
return maxWidth;
}Time: O(n) | Space: O(w)