Unit 6 · Heavy
The first genuinely recursive structure, where the recursion of the code mirrors the recursion of the data. Binary search trees are fast only while they stay balanced, and that caveat is the unit.
What a strong answer looks like
A strong Unit 6 answer states the ordering property over whole subtrees, not just children, and names the shape assumption behind any complexity it quotes.
Know
Height, depth, leaves, and internal nodes are defined relative to the root. Height measured in edges differs by one from height measured in nodes, so the convention must be stated.
Apply
State your convention before answering any height question.
Watch out
Mixing edge and node counts between parts of one answer.
Study move
Compute the height of a small tree under both conventions.
Know
In-order visits left, node, right and yields sorted order on a binary search tree. Pre-order suits copying, post-order suits deletion, and level-order needs a queue.
Apply
Choose the traversal by what the task requires rather than by habit.
Watch out
Deleting a tree pre-order, which frees a parent while its children are still reachable only through it.
Study move
Write all four traversals of one small tree and say which produces sorted output.
Know
The ordering property constrains entire subtrees, not merely immediate children. That is what lets search discard half the tree at each step.
Apply
Verify the property recursively when checking whether a tree is a valid BST.
Watch out
Checking only parent against children, which accepts trees that are not valid search trees.
Study move
Construct a tree where every parent-child pair is ordered but the tree is not a BST.
Know
Inserting sorted keys into an unbalanced BST produces a chain, and search degrades from logarithmic to linear. Self-balancing trees exist to prevent exactly this.
Apply
State the shape assumption whenever quoting logarithmic search.
Watch out
Quoting log n for a BST unconditionally. That holds only while the tree stays balanced.
Study move
Insert 1 through 7 in order into a plain BST and describe the resulting shape.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Write a method that checks whether a binary tree is a valid search tree, and explain why comparing each node only with its children is insufficient.
