Binary search trees
Binary search trees
- A binary search tree (BST) stores values so they stay sorted and are fast to find.
- Each node holds a value and links to up to two children: a
leftand aright. - The top node is the root. A node with no children is a leaf.
The BST rule
- For every node: everything in its left subtree is smaller, everything in its right is larger or equal (this lesson sends equal values right).
- This one rule is what lets you find a value by going left or right — never both.
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
A node
- We model a node as a small object with a
value, aleft, and aright. - A brand-new node has no children yet, so
leftandrightstart asNone.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
Inserting a value
- Start at the root. If the tree is empty, the new value becomes the root.
- If the value is smaller than the current node, go left; otherwise go right.
- Repeat until you reach an empty spot, and put the new node there.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
Traversals: the order you visit the nodes
- A traversal visits every node once. The three orders differ only in when the node's own value is taken:
| Traversal | Order | For the tree built from 5, 3, 8, 1, 4 |
|---|---|---|
| pre-order | node, left, right | 5, 3, 1, 4, 8 |
| in-order | left, node, right | 1, 3, 4, 5, 8: sorted |
| post-order | left, right, node | 1, 4, 3, 8, 5 |
- Because of the BST rule, in-order visits the values in sorted order.
- Each is naturally recursive. The example below writes pre-order and a node count; your task is in-order: move where
[root.value]goes.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def pre_order(root):
if root is None:
return []
return [root.value] + pre_order(root.left) + pre_order(root.right)
def size(root):
if root is None:
return 0
return 1 + size(root.left) + size(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(pre_order(root)) # [5, 3, 1, 4, 8]
print(size(root)) # 5
Searching is fast
- To find a value, compare it with the node, then go left or right — skipping half the tree each step.
- In a balanced tree this takes about
O(log n)steps, much faster than scanning a list. - A badly-shaped tree (values inserted already sorted) can degrade to a line —
O(n).
Common mistakes
- In a binary search tree: left child < node <= right child (equal values go right here).
- An unbalanced tree loses the speed advantage.
Now you try
- Build the three core operations:
insert,in_order, andcontains. - The
Nodeclass (and a workinginsert, where you need it) is provided. - Press Check answer to test it on several trees.
Tìm kiếm trong BST
Left is smaller, right is bigger — so each step skips half the tree.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root là (is) None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Node and a working insert are provided. Write in_order(root) that returns a list (danh sách) of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives [].
Nhấn Chạy để xem kết quả ở đây.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Node and a working insert are provided. Write contains(root, value) that returns True nếu value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search sang trái, otherwise search phải; an empty branch (None) means it is not there.
Nhấn Chạy để xem kết quả ở đây.