A tree is a structure that branches out, like a family tree or a folder structure. It starts at the root and each node can have children. Nodes with no children are leaves.
A BST follows one golden rule at every node: smaller values go left, larger values go right. This keeps the data organized so you can search it in O(log n) — just like binary search!
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
🚶 Traversals — visiting every node
Because trees branch, we use recursion to visit nodes. In-order traversal of a BST magically returns the values in sorted order!
def in_order(root):
if root is None:
return
in_order(root.left) # 1. left subtree
print(root.value) # 2. this node
in_order(root.right) # 3. right subtree
💡 Three traversal orders
In-order (left, node, right) → sorted output for a BST.
Pre-order (node, left, right) → copy/serialize a tree.
Post-order (left, right, node) → delete a tree safely.
✅ What you learned
A tree branches from a root; nodes have children, leaves have none.
A binary tree node has left and right children.
A BST keeps smaller left, larger right → fast O(log n) search.
In-order traversal of a BST prints values in sorted order.
🎮 Time to Practice!
Grow a tree, then climb it with recursion. 🌳
🌱
Task 1: Build a Tiny Tree
Easy
Write a Node class with value, left and right. Give the root (8) a left child of 3 and a right child of 10, then print the root, left and right values → 8, 3, 10.
Build this search tree — 8 at the root, 3 on its left (with children 1 and 6) and 10 on its right (with right child 14) — then write the in-order traversal (left, then node, then right). It prints the values in sorted order. That is not a coincidence!
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
root = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
def in_order(root):
if root is None:
return
in_order(root.left)
print(root.value)
in_order(root.right)
in_order(root)
📐
Task 3: Tree Height
Tricky
The height of a tree is the longest path from the root down to a leaf. Recursively: height = 1 + the taller of the two children, and an empty tree has height 0. Build the same tree as before and print its height → 3.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
root = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
def height(root):
if root is None:
return 0
return 1 + max(height(root.left), height(root.right))
print(height(root))
🏋️ Extra Practice — Algorithm Reps
Trees are everywhere: file folders, web pages, game decisions, databases. Grow a few of your own.
🌱
Task 4: Insert Into a Search Tree
Medium
In a binary search tree, smaller values go left and bigger go right. Write insert(node, value) recursively, build a tree from [8, 3, 10, 1, 6], then print the root, the root's left value and the root's right value.
8
3
10
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
root = None
for v in [8, 3, 10, 1, 6]:
root = insert(root, v)
print(root.value)
print(root.left.value)
print(root.right.value)
🔎
Task 5: Search a Tree
Medium
Write find(node, target) that returns True/False, going left when the target is smaller and right when it is bigger — never checking the other half. On the tree built from [8, 3, 10, 1, 6], print the search for 6 and for 5.
True
False
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def find(node, target):
if node is None:
return False
if node.value == target:
return True
if target < node.value:
return find(node.left, target)
return find(node.right, target)
root = None
for v in [8, 3, 10, 1, 6]:
root = insert(root, v)
print(find(root, 6))
print(find(root, 5))
🔢
Task 6: Count and Sum the Nodes
Medium
Write two tiny recursive functions on the same tree: count(node) returning how many nodes there are, and total(node) returning the sum of all values. Print both for the tree built from [8, 3, 10, 1, 6].
5
28
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def count(node):
if node is None:
return 0
return 1 + count(node.left) + count(node.right)
def total(node):
if node is None:
return 0
return node.value + total(node.left) + total(node.right)
root = None
for v in [8, 3, 10, 1, 6]:
root = insert(root, v)
print(count(root))
print(total(root))
🚶
Task 7: Three Ways to Walk a Tree
Tricky
Print the same tree three ways: pre-order (node, left, right), in-order (left, node, right — always sorted!) and post-order (left, right, node). Print each walk on one line using end=" ", with a blank print() between them.
8 3 1 6 10
1 3 6 8 10
1 6 3 10 8
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def pre_order(node):
if node is None:
return
print(node.value, end=" ")
pre_order(node.left)
pre_order(node.right)
def in_order(node):
if node is None:
return
in_order(node.left)
print(node.value, end=" ")
in_order(node.right)
def post_order(node):
if node is None:
return
post_order(node.left)
post_order(node.right)
print(node.value, end=" ")
root = None
for v in [8, 3, 10, 1, 6]:
root = insert(root, v)
pre_order(root)
print()
in_order(root)
print()
post_order(root)
print()
🪜
Task 8: Level by Level (BFS)
Tricky
Walk the tree top to bottom using a queue instead of recursion: take a node from the front, print it, then add its children to the back. Print the values of the tree from [8, 3, 10, 1, 6] in level order on one line.
8 3 10 1 6
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
root = None
for v in [8, 3, 10, 1, 6]:
root = insert(root, v)
queue = deque([root])
while queue:
node = queue.popleft()
print(node.value, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
print()
🧐
Task 9: Boss Level: Is It Really a Search Tree?
Boss
Write is_bst(node, low, high) that checks every node sits inside an allowed range (start with None for both limits). Test it on a proper tree (True) and on a broken one where a big value hides in the left branch (False).
True
False
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_bst(node, low=None, high=None):
if node is None:
return True
if low is not None and node.value <= low:
return False
if high is not None and node.value >= high:
return False
return is_bst(node.left, low, node.value) and is_bst(node.right, node.value, high)
good = Node(8, Node(3, Node(1), Node(6)), Node(10))
broken = Node(8, Node(3, Node(1), Node(9)), Node(10))
print(is_bst(good))
print(is_bst(broken))