Algorithms
Tree Algorithms
Difficulty: Intermediate
An invert-binary-tree problem famously got Max Howell rejected from Google in 2015, and the joke landed because the canonical solution is three lines of recursion. Trees show up everywhere in interviews precisely because they reward a...
Tree Algorithms
An invert-binary-tree problem famously got Max Howell rejected from Google in 2015, and the joke landed because the canonical solution is three lines of recursion. Trees show up everywhere in interviews precisely because they reward a particular kind of thinking: the answer for a node is almost always a function of the answers for its left and right subtrees, computed recursively, combined at the parent.
Tree Algorithms trains that decomposition habit across a wide range of problems. You will implement BST insert, search, delete, validation, and the kth-smallest in-order trick. You will compute lowest common ancestor in both a generic binary tree and a BST. You will measure height, diameter, and width, and walk through path-sum problems, root-to-leaf enumeration, and the deceptively tricky maximum-path-sum-between-any-two-nodes. Structural operations include invert, mirror check, flatten to linked list, and serialize and deserialize. The lesson finishes with reconstructing a tree from inorder plus preorder or inorder plus postorder.
In Trees: Binary Tree Fundamentals, you learned how nodes, children, and the four traversal orders work. Recursion Fundamentals gave you the call-stack mental model that every tree algorithm here relies on; tree recursion is essentially recursion with two recursive calls per frame.
Next, Graph Algorithms (Core) removes the tree assumption (no cycles, no shared nodes) and tackles the more general traversal problems that result.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement BST insert, search, and validate operations using recursive approaches.
Find the Lowest Common Ancestor in both a binary tree and a BST.
Calculate tree height and diameter using recursive decomposition.
Solve path-sum problems including root-to-leaf sums and all root-to-leaf paths.
Invert a binary tree and check whether two trees are mirrors of each other.
Explain tree algorithm complexity in terms of height h versus node count n.
Why This Matters
01
Tree problems represent 15-20% of coding interview questions at top companies, making them among the most important algorithm categories to master.
02
BST validation and Lowest Common Ancestor are classic interview problems that test recursive thinking and invariant reasoning under pressure.
03
Tree measurements (height, diameter, max path sum) build the recursive decomposition skill that transfers directly to dynamic programming.
04
Serialization and deserialization of trees test system design thinking alongside algorithmic skill, bridging two major interview categories.
Key Terms
7 terms you'll encounter in this lesson
BST property
For every node, all values in its left subtree are strictly less, and all values in its right subtree are strictly greater.
Lowest Common Ancestor (LCA)
The deepest node that is an ancestor of both given target nodes. In a BST the LCA is the first node where the two targets split into different subtrees.
Tree height
The number of edges on the longest root-to-leaf path. A single-node tree has height 0; an empty tree has height -1.
Tree diameter
The number of edges on the longest path between any two nodes. This path may or may not pass through the root.
Path sum
The sum of all node values along a path from the root to a leaf. The max-path-sum variant allows any node to any node.
In-order successor
The node with the smallest value greater than a given node in a BST. Found by going right once, then left as far as possible.
Balanced tree
A tree where the height difference between left and right subtrees of every node is at most 1 (AVL) or satisfies some similar constraint. Ensures O(log n) height.
Heads Up
Common misconceptions to watch out for
"The diameter of a tree always passes through the root"
The longest path can lie entirely within one subtree. Diameter is the maximum of left diameter, right diameter, and left height + right height + 2.
"BST validation only needs to check parent vs immediate child"
A node must be valid against ALL ancestors, not just its parent. Use min/max bounds that narrow as you recurse: each left child must be less than the parent AND less than all ancestors above.
"Tree operations are always O(log n)"
Tree operations are O(h) where h is the height. For a balanced tree h = O(log n), but for a skewed tree (shaped like a linked list) h = O(n). Always state complexity in terms of h when precision matters.