- Open Bookshelf Cover Page
- Preface
- Getting Started
- Introduction to Recursion
- Divide and Conquer Algorithms
- Dynamic Programming
-
Binary Trees
- Intro to Trees
- Binary Trees
- Types of Binary Trees
- Divide & Conquer in Tree Problems
- Practice: Binary Tree Height
- Tree Traversal: DFS and BFS
- Practice: Preorder Traversal
- Practice: Inorder Traversal
- Practice: Postorder Traversal
- Practice: Level Order Traversal
- Binary Search Tree
- Practice: Find Node in a BST
- Graphs
- Backtracking
- Conclusion
- Share on
Binary Search Tree
Binary Search Trees (BSTs) are a special type of binary tree that makes searching, adding, and deleting values very efficient. They're widely used in applications where quick data retrieval is essential, such as database indexing and in-memory sorting.
A binary search tree has the same properties of a binary tree that we've seen in this assignment plus a special one:
Ordered Elements: The left subtree of a node contains only nodes with values less than the parent node's value, while the right subtree contains only nodes with values greater than the parent node's value. The image below shows that the tree on the left is a valid BST, but the tree on the right isn't. While 4 is smaller than the root node's value 7, it is also smaller than its immediate parent's value 5. This violates the BST properties because each subtree must also be a valid BST.
Time and Space Complexities of Binary Search Tree Operations
Search: On average, searching for an element in a balanced BST takes O(log N) time, where N is the number of nodes. This efficiency comes from the fact that each step down the tree halves the search path, similar to binary search in a sorted array.
Insertion and Deletion: The average time complexities for inserting or deleting an element are O(log N), assuming the tree remains balanced.
However, the performance of a BST can degrade:
Unbalanced Trees: In the worst case, where the tree becomes skewed (like a linked list, either 'left-heavy' or 'right-heavy'), operations can slow down to O(N). This happens, for example, if you keep adding elements in ascending or descending order, leading to an unbalanced tree.
The space complexity for a BST is usually O(h), where h represents the tree's height, as it is much less common to perform a breadth-first search on the binary search tree.