Tree Terminology & the BST Invariant
You'll learn to
- -Define core tree vocabulary: root, parent, child, leaf, depth, and height
- -State the binary-search-tree invariant
- -Explain why the invariant makes search O(log n) on average but O(n) in the worst case
Every data structure so far in this course - arrays, linked lists, stacks, queues, hashmaps, heaps - has been essentially linear or flat. A tree is the first genuinely hierarchical structure: think of an org chart, a file system's folders, or the way an HTML document nests elements inside elements. Understanding tree vocabulary precisely now pays off for the rest of this tier, since trees, tries, and even graphs later on all build on the same core ideas.
Tree Vocabulary
- -Node - a single element in the tree, holding a value and references to its children.
- -Root - the single top-level node with no parent; every other node is reachable from it.
- -Parent / child - a direct connection one level apart; a node can have multiple children but exactly one parent (except the root, which has none).
- -Leaf - a node with no children - the "bottom" of a branch.
- -Depth - how many steps a node is from the root (the root has depth 0).
- -Height - the number of edges on the longest path from a node down to a leaf; the height of the whole tree is the height of its root.
The Binary-Search-Tree Invariant
A binary tree restricts every node to at most two children, conventionally called left and right. A binary search tree (BST) adds one crucial ordering rule on top of that shape: for every node, every value in its left subtree is smaller than the node's own value, and every value in its right subtree is larger. This single invariant, applied recursively at every node, is what turns a tree into something searchable.
Why the Invariant Makes Search Fast - Usually
Searching a BST for a value works exactly like the binary search you learned in Tier 4: compare the target against the current node, and the invariant tells you which entire subtree can be ignored. Go left if the target is smaller, right if it is larger, and you have discarded half the remaining nodes with a single comparison. If the tree is reasonably balanced (each subtree roughly the same size as its sibling), that halving happens at every level, giving O(log n) search - the same shape of guarantee as binary search on a sorted array.
The O(log n) average case assumes a roughly balanced tree. Nothing in the BST invariant itself prevents a badly skewed shape - inserting already-sorted data one element at a time (1, 2, 3, 4, 5...) produces a tree that is really just a linked list in disguise, with every node having only a right child. In that worst case, search degrades to O(n), exactly like a linear scan. Self-balancing variants (AVL trees, red-black trees) exist specifically to prevent this, though they are outside the scope of this tier.