Binary search tree is a binary tree where values are arranged so that lookup can be efficient.
For each node:
- Values in the left subtree are smaller than the node’s value
- Values in the right subtree are larger than the node’s value
This ordering makes it possible to search by choosing either the left or right branch at each step.
Common operations:
- Search
- Insert
- Delete
- Traverse in sorted order
Average time complexity for search, insert, and delete is O(log n) when the tree is balanced. In the worst case, an unbalanced binary search tree can degrade to O(n), similar to a linked list.
Balanced tree variants, such as AVL trees and red-black trees, keep the tree height under control.
flowchart TD Eight["8"] --> Three["3"] Eight --> Ten["10"] Three --> One["1"] Three --> Six["6"] Ten --> Fourteen["14"]
Anki
id: binary-search-tree-definition deck: Computer Science::Data Structures tags: data-structures tree binary-search-tree
Q: How does a binary search tree decide whether to search left or right? A: If the target value is smaller than the current node, search left; if it is larger, search right.
id: binary-search-tree-worst-case deck: Computer Science::Data Structures tags: data-structures tree binary-search-tree complexity
Q: What goes wrong if values are inserted into a binary search tree in sorted order? A: The tree can become a long chain, making search behave like scanning a linked list.