Data with branches
Lists are a line. A tree branches: one item at the top, and each item can have items below it.
Think of it like this: A family tree, folders on your computer (a folder holds files and other folders), or a company chart: the CEO at the top, managers below, their teams below them.
Tree words
| Word | Meaning |
|---|---|
| node | one item in the tree |
| root | the node at the very top |
| children / parent | the nodes directly below a node / the node directly above |
| leaf | a node with no children |
| height | the number of levels (the longest path from the root down, counting nodes) |
| subtree | a node together with everything below it – a smaller tree |
Binary trees
In a binary tree each node has at most two children: a left and a right one.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print(root.value, root.left.value, root.right.value)
print("children of 2:", root.left.left.value, root.left.right.value)Output
1 2 3 children of 2: 4 5
Remember: Every subtree is itself a tree. That's why recursion fits trees so perfectly: solve it for the left subtree, solve it for the right subtree, then combine.