Trees
Branching data.
Not all data fits in a line. A family tree branches. So do the folders on your computer, and the menus in an app. A tree is a data structure where each item can have children, which can have children of their own.

- Not everything is a line
- Family trees, folders, menus
- Items with children
Tree words
A tree starts at the root, the node at the top. Each node can have children below it, and every node except the root has exactly one parent. Nodes with no children are called leaves. And the height of a tree is the number of levels from the root down to the deepest leaf.
A binary tree
A binary tree is a tree where each node has at most two children, called left and right. Our tree node class holds a value and two links. A helper file builds a sample tree for us, and a picture of it. Here we print the picture, and look at a few of its parts. Run it.
from tree import sample, PICTURE
root = sample()
print(PICTURE)
print("root:", root.value)
print("children:", root.left.value, root.right.value)
print("a leaf:", root.left.left.value, root.left.left.left) 8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
root: 8
children: 3 10
a leaf: 1 NoneAlso uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'Summary
A tree has a root, children, and leaves. A binary tree gives each node at most a left and a right child. Next, visiting every node in a tree.
Key takeaways- Root, children, leaves
- Binary: left and right
- Height = levels