Unit 24: Trees
Branching structures.
Unit 24 of 31 in Python for kids. Its 5 lessons are Branches, Walking a Tree, Trees That Sort Themselves, Searching Fast and Tree Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🌳 Branches
A chain that splits
A chain node points at one other node. A tree node points at several — its children. The node at the top is the root, and nodes with no children are leaves.
Python
class Node:
def __init__(self, value):
self.value = value
self.children = []
root = Node("animals")
root.children.append(Node("cat"))
root.children.append(Node("dog"))
print(root.value)
for child in root.children:
print(" -", child.value)It prints
animals - cat - dog
Trees are everywhere
Folders inside folders, the menu on a website, the pieces of a web page — all trees. Anything where one thing contains several others is a tree.
Python
tree = {
"school": {
"year5": {},
"year6": {"art": {}},
}
}
print(list(tree))
print(list(tree["school"]))
print(list(tree["school"]["year6"]))It prints
['school'] ['year5', 'year6'] ['art']
Two pointers instead of a list
A binary tree allows at most two children, called left and right. That limit is what makes the clever tricks in the next lessons possible.
Python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
root = Node(5)
root.left = Node(3)
root.right = Node(8)
print(root.value)
print(root.left.value, root.right.value)It prints
5 3 8
Try it yourself
What is a leaf?
- The node at the top
- A node with no children
- A node with two children
- The biggest value
What does this print?
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
r = Node(1)
r.left = Node(2)
r.left.right = Node(3)
print(r.left.right.value)
print(r.right)Answer them in the app
🥾 Walking a Tree
Recursion fits trees perfectly
Every branch of a tree is itself a smaller tree. So a function that handles a node just calls itself on the children — and the base case is running out of tree.
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
root = Node(1)
root.left = Node(2)
root.right = Node(3)
def show(node):
if node is None:
return
print(node.value)
show(node.left)
show(node.right)
show(root)It prints
1 2 3
Where you print decides the order
Print *before* the children and you go top-down (pre-order). Print *between* them and you get in-order. Print *after* both and you get post-order. Same walk, three orders.
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
root = Node(2)
root.left = Node(1)
root.right = Node(3)
def in_order(node):
if node is None:
return
in_order(node.left)
print(node.value)
in_order(node.right)
in_order(root)It prints
1 2 3
Counting and measuring
The same shape counts nodes or measures how tall the tree is. Height is 1 plus the taller of the two sides.
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
root = Node(1)
root.left = Node(2)
root.left.left = Node(4)
def count(node):
if node is None:
return 0
return 1 + count(node.left) + count(node.right)
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
print(count(root))
print(height(root))It prints
3 3
Try it yourself
In pre-order, when is a node printed?
- After both its children
- Before either of its children
- Between its children
- Only if it is a leaf
What does this print?
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
r = Node("a")
r.left = Node("b")
r.right = Node("c")
def post(node):
if node is None:
return
post(node.left)
post(node.right)
print(node.value)
post(r)Answer them in the app
🔍 Trees That Sort Themselves
One rule changes everything
A binary search tree keeps one promise: everything on the left is smaller than the node, everything on the right is bigger. Nothing else is new — but that rule makes finding things fast.
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
root = Node(8)
root.left = Node(3)
root.right = Node(10)
print(root.left.value < root.value)
print(root.right.value > root.value)It prints
True True
Adding follows the rule
To insert, start at the root and go left when smaller, right when bigger, until you find an empty spot. The value lands exactly where the rule says it must.
Python
class Node:
def __init__(self, v):
self.value = v
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 n in [8, 3, 10]:
root = insert(root, n)
print(root.value, root.left.value, root.right.value)It prints
8 3 10
In-order always comes out sorted
This falls straight out of the rule: everything smaller is on the left, so visiting left-then-node-then-right visits the values in order. A BST sorts as you build it.
Python
class Node:
def __init__(self, v):
self.value = v
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 in_order(node):
if node is None:
return
in_order(node.left)
print(node.value)
in_order(node.right)
root = None
for n in [5, 2, 8, 1]:
root = insert(root, n)
in_order(root)It prints
1 2 5 8
Try it yourself
Where does 6 go in a BST whose root is 5?
- Left
- Right
- It replaces the root
- It cannot be added
Answer it in the app
⚡ Searching Fast
Half the tree disappears at every step
Looking for a value, you compare once and then ignore an entire side of the tree. That is why a BST search is quick even when the tree is huge.
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
root = Node(5)
root.left = Node(2)
root.right = Node(8)
def find(node, wanted):
if node is None:
return False
if node.value == wanted:
return True
if wanted < node.value:
return find(node.left, wanted)
return find(node.right, wanted)
print(find(root, 8))
print(find(root, 7))It prints
True False
Count the steps yourself
Here the tree holds 7 values, and finding one takes 3 comparisons at most — because each step throws away half of what is left.
Python
class Node:
def __init__(self, v):
self.value = v
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 n in [4, 2, 6, 1, 3, 5, 7]:
root = insert(root, n)
def steps(node, wanted, count=1):
if node.value == wanted:
return count
if wanted < node.value:
return steps(node.left, wanted, count + 1)
return steps(node.right, wanted, count + 1)
print(steps(root, 7))
print(steps(root, 4))It prints
3 1
Finding the smallest and biggest
The smallest value is as far left as you can go, and the biggest as far right. No searching needed at all.
Python
class Node:
def __init__(self, v):
self.value = v
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 n in [5, 2, 8, 1, 9]:
root = insert(root, n)
node = root
while node.left:
node = node.left
print(node.value)
node = root
while node.right:
node = node.right
print(node.value)It prints
1 9
Try it yourself
A balanced BST holds 1000 values. Roughly how many steps to find one?
- About 1000
- About 500
- About 10
- Exactly 1
Answer it in the app
🏆 Tree Master
Try it yourself
What does this print?
Python
class Node:
def __init__(self, v):
self.value = v
self.left = None
self.right = None
r = Node(2)
r.left = Node(1)
r.right = Node(3)
def pre(node):
if node is None:
return
print(node.value)
pre(node.left)
pre(node.right)
pre(r)Answer it in the app