Lesson 6.1
Tree Terminology
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.
Lessons and exercises
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.
Lesson 6.2
Traversals
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.
Lesson 6.3
Binary Search Trees
The ordering property constrains entire subtrees, not merely immediate children. That is what lets search discard half the tree at each step.
Lesson 6.4
Balance and Degeneration
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.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic