A data tree looks like an upside-down garden tree. It starts with one root at the top or bottom, then splits into branches.
Every circle in the tree is a node. A node can have child nodes. A node above a child is its parent. A node with no children is called a leaf.
A family of folders
Think about folders on a computer. The Pictures folder may have Pets and Holidays inside it. Holidays may have Beach and Mountains. This shape is a tree because one folder can lead to smaller groups.
Binary trees have two seats
In a binary tree, each node can have at most two children. We often call them left and right.
A binary search tree adds a sorting rule. Smaller values go left. Bigger values go right. To find 7, compare it with the root. Choose left or right, then repeat. We can skip whole branches that cannot contain 7.
Ways to walk through a tree
- Depth-first search follows one branch deeply before coming back.
- Breadth-first search visits one level at a time.
- Both methods can visit every node, but they choose a different order.
Trees are useful for menus, folders, family relationships, game choices, and search systems. They are good whenever information naturally splits into smaller groups.
Keep the tree healthy
A very lopsided tree can become a long chain. A balanced tree keeps its branches closer in height, so finding things usually takes fewer steps.
class Node:
def __init__(self, name):
self.name = name
self.children = []
animals = Node("Animals")
animals.children.append(Node("Cats"))
animals.children.append(Node("Dogs"))
for child in animals.children:
print(child.name)Your tiny challenge
Draw a root named Animals. Add Cats and Dogs as children. Give each child two breeds. Point to the parents, children, and leaves. You have made a small data tree.