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.
Searching a BST
Left is smaller, right is bigger — so each step skips half the tree.
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root 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.
実行ボタンをクリックして出力を確認してください。
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
Node and a working insert are provided. Write in_order(root) that returns a リスト 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 [].
実行ボタンをクリックして出力を確認してください。
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search 左へ, otherwise search 正しい; an empty branch (None) means it is not there.
実行ボタンをクリックして出力を確認してください。