Inserting into a BST
Build a binary search tree.
The BST Ordering Rule
A Binary Search Tree (BST) is a binary tree with one extra rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.
This ordering is what lets us search, insert, and delete in time proportional to the tree's height.
Where a Value Belongs
To insert, we start at the root and compare. If the new value is smaller, we go left; if larger, we go right.
We repeat until we reach an empty spot (NULL), which is exactly where the new node belongs.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/All lessons in this course
- Tree Nodes and Structure
- Inserting into a BST
- Traversals
- Searching and Freeing