Intuition The ONE idea of the whole topicA Binary Search Tree is just a branching diagram of keys where, at every fork, everything to the left is smaller and everything to the right is bigger. That single left-small/right-big rule lets you find, add, or remove a value by walking one path from the top — throwing away half the possibilities at each step.
Before you can read the parent note, you need every word and symbol it leans on. This page builds them from nothing , in an order where each new idea only uses ideas already defined. Read top to bottom.
A key is the single comparable value stored inside a spot in our structure. Think of a numbered ticket: 50 30 70
We need keys because the whole magic of a BST is comparing them (< > =
Definition The three comparison signs
a < b a less than b a a > b a greater than b a a = b a equals b
Intuition Picture — the number lineLay keys on a horizontal line. "Left on the line" = = <
Why the topic needs these: every BST decision is one comparison that picks a direction. This is the single tool that turns a shapeless pile of keys into a searchable order — the same idea used in Binary Search on Sorted Array .
These come from ordinary trees. If you have met them, skim; if not, this is your foundation. See also Binary Tree — terminology & traversals .
Definition The vocabulary of a tree
Node : a circle holding one key (from §1).Edge : a line connecting two nodes — a "who-points-to-whom" link.Parent / child : if an edge goes down from A B A B Root : the one node at the very top with no parent — the entry point.Leaf : a node with no children — the bottom of a branch.Binary : every node has at most two children, named left and right.
Intuition Picture — a family tree upside downThe root is the ancestor at the top; edges branch downward; leaves are the youngest with no descendants. Notice trees in computing grow downward .
Why the topic needs these: a BST is a binary tree with the ordering rule bolted on. Without "at most two children named left/right" the phrase "left subtree" has no meaning.
Pick any node x subtree of x is x all nodes you can reach by walking downward from x x.left subtree means "the left child of x and everyone beneath it ."
Cover the rest of the tree with your hand and leave only x x
Why the topic needs this: the BST property talks about whole subtrees , not just direct children (all keys in x . left < k subtree of 10, not a direct child.
Definition BST property (now every word is defined)For every node x k
all keys in the left subtree of x < k
all keys in the right subtree of x > k
"Every node" and "subtree" (§4) mean this holds recursively, all the way down — not just for the two direct children.
Intuition Why "recursively for every node"?A picture where each fork is locally correct can still be globally broken (the 6-under-10 counter-example). The property must be true at each node using the whole subtree below it. That is why validation needs a (low, high) range, not a child-vs-child check.
None (also written null) means "there is no node here " — an empty pointer. A leaf's left and right are both None. Searching that reaches None means "the key you wanted is not present."
Draw missing children as a small dashed square labelled None. These empty squares are the exact slots where a new key gets attached during insert — the place the search "falls off."
Why the topic needs this: insert works by descending until it hits a None, and search returns "not found" precisely when it lands on None. The empty slot is a first-class idea, not an afterthought.
Definition Height and depth
Depth of a node = number of edges from the root down to it .Height h deepest node = length of the longest root-to-leaf path.
See Tree Height vs Depth for the two-way view.
Intuition Picture — count the steps downh its cost is h .
log 2 n n log 2 n "how many times can I halve n If halving each step is what a BST does, then the number of steps to reach the answer is about log 2 n n = 8 → 4 → 2 → 1 3 log 2 8 = 3
Why the topic needs log balanced BST halves the remaining nodes at each fork, so a path is only about log 2 n degenerate "stick" (keys inserted already sorted) has height n − 1 AVL Tree and Red-Black Tree exist.
Definition Big-O, in one lineO ( something ) how the work grows as the input grows, ignoring constant factors. O ( h ) O ( log n ) O ( n )
Plot cost vs n O ( log n ) O ( n ) if it stays balanced, and slide onto the diagonal if it degenerates.
Why the topic needs it: every cost claim in the parent (T search = O ( h ) O ( log n ) O ( n )
Definition In-order traversalA recipe that visits nodes in the order left subtree → node → right subtree , applied recursively. See Recursion on Trees .
Intuition Picture — read left first, alwaysBecause left is always smaller (§5) and right always larger, "do all the smaller stuff, then me, then all the larger stuff" spits out keys in strictly increasing order . This is your correctness checkpoint: if the in-order list isn't sorted, it's not a valid BST.
Comparisons less greater equal
Binary Tree - root edges leaves
BST property left small right big
Subtree - node and all below
Cover the right side and answer each before revealing.
What does a < b a left (smaller) side — the <
What is a leaf? A node with no children (both left and right are None).
What is the subtree of node x x and every node reachable downward from it — not just its direct children.
State the BST property in full. For every node with key k < k > k
What does landing on None during a search mean? The key is not present (you fell off the tree).
What is the height h The number of edges on the longest root-to-leaf path.
What does log 2 n How many times you can halve n 1
Why is a balanced BST search O ( log n ) Each comparison discards half the nodes, so the path length is about log 2 n
When does height become n − 1 When keys are inserted already sorted, building a one-sided "stick."
Why does in-order traversal come out sorted? It visits all smaller keys (left), then the node, then all larger keys (right), recursively.
Ready? Head back to the parent BST note and the property will read like plain English.
