Binary Tree Algorithms

What's being tested

Binary tree traversal under changing constraints: visibility, deletion/replacement, width indexing, reconstruction, and distance relationships. Interviewers are probing whether you can choose DFS, BFS, recursion, hashing, or parent pointers deliberately, while handling null roots, skewed trees, duplicate values, and overflow.

Patterns & templates

• Right-side view BFS — level-order traversal, append last node per level; O(n) time, O(w) space where w is max width.

• Right-side view DFS — visit root-right-left, record first node at each depth; cleaner recursion, but watch stack depth on skewed trees.

• Tree deletion / replacement — for BST-style deletion, handle 0/1/2 children; use inorder successor/predecessor; return updated subtree root.

• Maximum width indexing — BFS with complete-tree positions: left 2*i, right 2*i+1; normalize each level to avoid integer overflow.

• Build tree from traversals — preorder + inorder or inorder + postorder; hashmap value-to-index gives O(n) time, recursive bounds prevent slicing overhead.

• Distance-k pairs / nodes — convert tree to undirected graph via parent map, then BFS; or use postorder distances for pair counting.

• Validation mindset — confirm unique node values for reconstruction; malformed traversal arrays should fail fast or be documented as unsupported.

Common pitfalls

Pitfall: Treating width as node count per level; width includes missing positions between the leftmost and rightmost non-null nodes.

Pitfall: Reconstructing from traversal arrays with duplicates without extra identity information; the tree is not uniquely determined.

Pitfall: Forgetting to return the new root after deletion, especially when deleting the original root node.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.