Trees and traversals

Recursion over a hierarchy. The choice of traversal is usually the whole solution.

Trigger in the prompt: Anything with a root, children, depth or levels.

easyBalanced Binary Tree

Decide whether every node's two subtrees differ in height by at most one.

Trigger

'Balanced', 'height difference at most one' — the AVL invariant.

Approach
  1. Naive: compute height at every node — O(n²).
  2. Better: one postorder pass returning the height, or a sentinel meaning 'already unbalanced'.
  3. Early exit: once a subtree reports unbalanced, propagate it up without more work.
Target complexity

O(n) time, O(h) space.

Pitfall

The O(n²) version, recomputing heights. The interviewer is waiting for the single-pass fix.

Say it out loud

“The obvious version recomputes the height at every node, which is quadratic. I'll fold the check into the height computation: the recursion returns the height, or minus one meaning already unbalanced, so one pass answers it.”

Solve on LeetCode
easyDiameter of Binary Tree

Find the longest path between any two nodes, which need not pass through the root.

Trigger

'Longest path anywhere in the tree' — the give-away for postorder returning two things.

Approach
  1. Key insight: at each node, the best path through it is left height + right height.
  2. So the recursion returns the height, and updates a running maximum as a side effect.
  3. Two different quantities: what you return (height) and what you record (diameter).
Target complexity

O(n) time, O(h) space.

Pitfall

Trying to return both values and getting confused about which one propagates. Return the height; keep the diameter in an enclosing variable.

Say it out loud

“The trick here is that the value I return and the value I'm looking for are different. Each call returns its height to its parent, but along the way it updates the best diameter seen, which is the sum of the two child heights. One traversal, linear time.”

Solve on LeetCode
easyInvert Binary Tree

Mirror a binary tree, swapping every node's left and right subtree.

Trigger

'Mirror', 'invert', 'reflect' on a tree.

Approach
  1. Base case: an empty node returns nothing.
  2. Swap the two children, then recurse into both.
  3. Mention the iterative version with a queue if depth could be a problem.
Target complexity

O(n) time, O(h) space for the stack.

Pitfall

Recursing before swapping and then swapping the already-processed children — it still works, but be clear about which order you meant.

Say it out loud

“Every node needs the same operation, so this is a straight DFS. I swap the children and recurse. Space is the recursion stack, O(h), which on a degenerate tree is O(n).”

Solve on LeetCode
easyMaximum Depth of Binary Tree

Return the number of nodes on the longest root-to-leaf path.

Trigger

'Depth', 'height', 'how many levels'.

Approach
  1. Depth of a node is one plus the max of its children's depths — that is postorder.
  2. Base case: an empty node has depth zero.
  3. BFS alternative counts levels; mention the space difference.
Target complexity

O(n) time, O(h) space.

Pitfall

Confusing height (node to leaf) with depth (root to node).

Say it out loud

“The parent needs a value computed from its children, so this is postorder. Recursively it's one line. I could also do it level by level with BFS, but that costs O(width) instead of O(height), and the bottom level can hold half the nodes.”

Solve on LeetCode
easySubtree of Another Tree

Decide whether one tree appears as a subtree of another.

Trigger

'Contains', 'appears as a subtree'.

Approach
  1. Two functions: one walks the big tree, one checks structural equality from a given root.
  2. At each node of the big tree, if the values match, run the equality check.
  3. Mention the serialisation trick: serialise both with null markers and do substring search — O(n + m) with KMP.
Target complexity

O(n·m) naively; O(n + m) with the serialisation approach.

Pitfall

Serialising without null markers for missing children — different trees then produce the same string.

Say it out loud

“The direct version is nested DFS, so O(n times m). There's a neater one: serialise both trees in preorder with explicit null markers, and the question becomes substring search, which is linear with KMP. The null markers matter — without them two different shapes can serialise identically.”

Solve on LeetCode
mediumBinary Tree Level Order Traversal

Return the node values grouped by level, top to bottom.

Trigger

'Level by level', 'by depth', 'row by row'.

Approach
  1. BFS with a queue.
  2. The trick that separates levels: capture `len(queue)` before the inner loop and iterate exactly that many times.
  3. Everything appended during that inner loop belongs to the next level.
Target complexity

O(n) time, O(width) space.

Pitfall

Not freezing the queue length. You get a correct BFS but lose the level boundaries.

Say it out loud

“Standard BFS, with one detail that does all the work: I snapshot the queue length before the inner loop, so everything I dequeue in that pass is exactly one level and everything I enqueue belongs to the next.”

Solve on LeetCode
mediumBinary Tree Right Side View

Return the values visible when looking at the tree from the right.

Trigger

'What you see from the side', 'the rightmost node of each level'.

Approach
  1. It is level-order, taking the last element of each level.
  2. Alternative: DFS visiting right before left, recording the first node seen at each new depth.
  3. The DFS version is O(h) space instead of O(width).
Target complexity

O(n) time, O(width) with BFS or O(h) with DFS.

Pitfall

Assuming the rightmost node is always a right child. It can be a left child, if the right subtree is shorter.

Say it out loud

“It's the last node of each level. BFS makes that obvious, but DFS visiting right first is nicer on space: the first time I reach a new depth, that node is the one visible from the right.”

Solve on LeetCode
mediumBuild Tree from Preorder+Inorder

Rebuild a binary tree given its preorder and inorder traversals.

Trigger

'Reconstruct the tree from two traversals'.

Approach
  1. Preorder's first element is the root. Find it in inorder: everything left of it is the left subtree, everything right is the right subtree.
  2. That gives the sizes, which gives the preorder slices for each side.
  3. The O(n) version: a hash map from value to inorder index, plus index bounds instead of slicing.
Target complexity

O(n) time and space with the index map; O(n²) with naive search and slicing.

Pitfall

Slicing the arrays at every level — that is O(n²) time and space. Pass indices instead.

Say it out loud

“The root comes from preorder, and inorder tells me how the remaining nodes split. Doing that naively costs a linear search plus a slice per node, so quadratic. I'll precompute a map from value to inorder index and pass bounds instead of slices, which makes it linear.”

Solve on LeetCode
mediumKth Smallest Element in a BST

Return the k-th smallest value in a binary search tree.

Trigger

'k-th smallest' plus the input being a BST.

Approach
  1. Inorder on a BST yields sorted order — say that first, it is the whole insight.
  2. Walk inorder with a counter and stop as soon as you have seen k nodes.
  3. The iterative version with an explicit stack makes the early stop natural.
Target complexity

O(h + k) time, O(h) space.

Pitfall

Materialising the whole inorder list and indexing. Correct, but O(n) when O(h + k) was available.

Say it out loud

“Inorder on a BST gives sorted order, so this is a traversal with an early exit. I'll write it iteratively with a stack, which makes stopping at k natural — that's O(height plus k) rather than walking the whole tree.”

Solve on LeetCode
mediumLCA of a BST

Find the deepest node that has both given nodes as descendants, in a BST.

Trigger

'Lowest common ancestor' plus the input being a search tree.

Approach
  1. Use the BST invariant instead of searching: compare both targets against the current value.
  2. Both smaller → go left. Both larger → go right. Otherwise this node is the split point.
  3. Iterative, so O(1) space.
Target complexity

O(h) time, O(1) space iteratively.

Pitfall

Solving it as if the tree were unordered. That works but throws away the property the problem handed you.

Say it out loud

“Because it's a BST I don't need to search — I can decide direction by comparison. The first node where the two targets fall on opposite sides, or where one equals the node, is the lowest common ancestor. That's O(height) and constant space.”

Solve on LeetCode
mediumValidate Binary Search Tree

Decide whether a binary tree satisfies the BST ordering property everywhere.

Trigger

'Is this a valid BST' — the classic trap.

Approach
  1. Say the trap out loud: comparing a node only with its parent is wrong.
  2. Carry a (low, high) bound down the recursion; each node must lie strictly inside it.
  3. Going left tightens the upper bound, going right tightens the lower bound.
  4. Alternative: an inorder walk must be strictly increasing.
Target complexity

O(n) time, O(h) space.

Pitfall

The parent-only comparison. It accepts trees where a deep node violates an ancestor's bound.

Say it out loud

“The mistake I want to avoid is comparing each node only with its parent — that misses violations against a distant ancestor. I'll pass a lower and upper bound down the recursion. Equivalently, an inorder traversal of a valid BST is strictly increasing, which is a nice one-line check.”

Solve on LeetCode
hardBinary Tree Maximum Path Sum

Find the maximum sum along any path in the tree; the path need not touch the root.

Trigger

'Maximum path sum', values can be negative.

Approach
  1. Same shape as diameter: what I return and what I record are different.
  2. Return to the parent: node value plus the better single branch, clamped at zero.
  3. Record globally: node value plus both branches (both clamped at zero).
  4. Clamping at zero is how negative subtrees get dropped.
Target complexity

O(n) time, O(h) space.

Pitfall

Forgetting the clamp. With negative values, including a harmful branch lowers the answer.

Say it out loud

“This is diameter with weights. The value I hand my parent is the best single downward path, because a parent can't use both my branches. The value I record is both branches plus me. And I clamp each branch at zero, so a negative subtree is simply not taken.”

Solve on LeetCode
hardSerialize and Deserialize Binary Tree

Encode a tree as a string and rebuild it exactly.

Trigger

'Serialise', 'encode and decode', 'persist the tree'.

Approach
  1. Preorder with an explicit marker for null — the marker is what makes it unambiguous.
  2. Deserialise by consuming tokens in the same order, recursively.
  3. Explain why preorder: the parent arrives before its children, so you can build top-down.
Target complexity

O(n) for both directions, O(n) space.

Pitfall

Omitting the null markers. Without them the string does not determine the shape.

Say it out loud

“I'll use preorder with an explicit null marker. Preorder because the root arrives first, so I can build top-down as I consume tokens. The null markers are what make the encoding unambiguous — without them, different shapes serialise to the same string.”

Solve on LeetCode