Searching and Freeing
Find nodes and release memory.
Searching a BST
Searching exploits the ordering rule. At each node we compare the target with the node's value and move into just one subtree.
Because we discard half the remaining nodes at each step, search costs scale with the tree's height, not its size.
Recursive Search
The recursive search has two base cases: an empty subtree means not found, and a matching value means found.
Otherwise we recurse left or right depending on the comparison.
Node *search(Node *root, int target) {
if (root == NULL || root->value == target)
return root;
if (target < root->value)
return search(root->left, target);
return search(root->right, target);
}All lessons in this course
- Tree Nodes and Structure
- Inserting into a BST
- Traversals
- Searching and Freeing