BST rule
- Algorithms course
- Intermediate
- Lesson 29/80
- 4 min
Left child smaller, right child larger in a BST.
BST property
A binary search tree (BST) is a binary tree where all values in a node's left subtree are smaller than the node's value, and all values in the right subtree are larger.
Thanks to this rule, search, insert and delete are O(log n) (when balanced). Inorder traversal gives increasing order.
The BST is a fundamental structure for fast search on sorted data. If unbalanced it degrades to O(n).
BST property
The BST rule is recursive: every subtree is also a BST. All values in the left subtree are smaller than the root, all in the right subtree are larger.
This applies binary-search logic to searching: if the target is smaller than the root go left, if larger go right. Each step halves the search space.
A balanced BST has height log n; each search takes at most that many steps.
Practice Check BST
Write is_bst(node, lo, hi). Recursively check node value is in (lo, hi). Print True with root = Node(5); root.left = Node(3); print(is_bst(root, -9999, 9999)).
Starter code
def is_bst(node, lo, hi):
# Check BSTSample solution
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def is_bst(node, lo, hi):
# Check BST
if node is None:
return True
if not (lo < node.val < hi):
return False
return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)
root = Node(5)
root.left = Node(3)
print(is_bst(root, -9999, 9999))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What are left subtree values in a BST?
- Larger than the node
- Smaller than the node Correct answer
- Equal
- Random
Explanation: Smaller than the node
2 Search direction
if target ____node.val: go leftif target <node.val: go leftExplanation: < is right.
3 BST rule: match the terms
| Term | Meaning |
|---|---|
Left subtree |
Smaller |
Right subtree |
Larger |
Inorder |
Increasing |
Balanced |
O(log n) |