Lesson 08 of 16 · 39:39
Binary trees & BSTs
A tree is a hierarchy of nodes. Every child begins a smaller tree, which is why recursive definitions fit so naturally. The most useful quantity is height: it controls how many decisions a search makes and how much recursion stack a traversal can consume.
Tree interviews become easier when every helper has a local contract. Instead of trying to solve the whole tree at once, ask what fact one call should return about the subtree rooted at its node—height, validity, a path sum, or a transformed root.
What you should be able to do after this lesson
- Translate tree shape into height
- Choose traversal order from data dependencies
- Carry BST bounds for entire subtrees
The mental model
A tree problem is usually a traversal plus a per-node contract. Choose when the node is processed and what each subtree must return.
Recognize it when: Use tree traversal when answers depend on descendants, ancestry, root-to-leaf paths, subtree summaries, hierarchical levels, or ordered BST ranges.
The invariant to say aloud: Each node is visited under the intended order, and every completed subtree returns the exact summary promised to its parent.
Learn the ideas one at a time
Concept 1 of 5
Shape and storage
Watch from 0:00 ↗Binary nodes have up to two children. Complete trees pack levels left-to-right and map cleanly to arrays; height controls recursion depth and many operation costs.
A binary node has at most two children, but shape determines performance. Complete trees fill levels left-to-right and can be stored densely in arrays. A perfect tree has every internal node fully populated. A balanced tree keeps height near log n; a skewed tree can have height n.
Walk through an example
At zero-based array index i, children of a complete-tree node live at 2i+1 and 2i+2. Missing interior positions in an arbitrary tree break that compact mapping and waste array slots.
In an interview
Give complexity in terms of height h first. Then say h = O(log n) only when a balance guarantee exists.
Concept 2 of 5
DFS orders
Watch from 7:25 ↗Preorder processes node-left-right, inorder left-node-right, and postorder left-right-node. The position of ‘process node’ is the whole distinction.
Depth-first traversal completes one subtree before moving to the next. Preorder processes a node before children, inorder between left and right, and postorder after both. The order should follow when the required information becomes available, not a memorized acronym.
Walk through an example
For root 2 with left 1 and right 3: preorder is 2,1,3; inorder is 1,2,3; postorder is 1,3,2. Inorder of a valid BST produces sorted values.
In an interview
Use preorder to pass information downward or serialize, inorder for BST order, and postorder when a parent combines completed child results.
Concept 3 of 5
BFS / level order
Watch from 13:36 ↗A queue processes nodes in discovery order, preserving depth layers. Enqueue children after removing their parent.
Breadth-first traversal uses a queue to process nodes in nondecreasing depth. To keep level boundaries, capture the queue length before processing a level; newly enqueued children belong to the next level and should not change the current iteration count.
Walk through an example
Queue [root] has level size 1. Remove root and enqueue its two children. The next saved size is 2, so those children are processed together as depth 1.
In an interview
Explain whether you need nodes, levels, or shortest depth. That determines whether the queue stores only nodes or also depth metadata.
Concept 4 of 5
Iterative DFS
Watch from 15:20 ↗An explicit stack replaces recursive frames. Push children in reverse of the order you want to visit because the last pushed is removed first.
An explicit stack stores the same unfinished work that recursive frames would hold. Because a stack reverses insertion order, push the right child before the left when you want the left processed first. More complex postorder traversals may need a visited flag or two stacks.
Walk through an example
Push root. Pop it, then push right and left. Left is now on top and is processed next, matching recursive preorder root-left-right.
In an interview
State what one stack entry means and when a node is considered processed; this prevents marking or producing output at the wrong time.
Concept 5 of 5
Binary search trees
Watch from 23:58 ↗Every node partitions values into ordered left and right regions. Balanced height gives O(log n) search; a skewed BST can degrade to O(n).
A BST partitions an entire subtree: every value left of a node must satisfy the lower side of its ordering rule, and every value right must satisfy the upper side. Checking only a node against its immediate children misses deeper violations. Carry allowable bounds down the tree instead.
Walk through an example
A value 6 in the left subtree of root 5 is invalid even if it is less than its immediate parent 7. The inherited upper bound 5 exposes the violation.
In an interview
Clarify the duplicate policy and validate with ancestor bounds. Search is O(h), which is logarithmic only for a balanced tree.
Before you call this lesson done
- Define the helper’s subtree contract
- Choose preorder/inorder/postorder from dependency
- Use a queue for levels
- Express costs using height h
