What is it? #
A tree is a set of nodes where each node has one parent and any number of children. One node at the top — the root — has no parent.
There are no loops. Follow parents upwards from any node and you always reach the root. That property is what makes trees easy to reason about and easy to walk.
The vocabulary is small: root at the top, leaves at the bottom with no children, depth is the distance from the root, and height is the distance from a node down to its deepest leaf.
A binary tree restricts each node to at most two children. That restriction unlocks useful structures, including the binary search tree and heap covered next.
Think of it like this #
A folder on your computer. It contains files and other folders, which contain more of both. There is one top-level folder, no folder is inside itself, and every file has exactly one path back to the top.
An organisation chart works the same way: one head, each person reporting to one manager, no circular reporting.
Simple example #
A product category tree: Electronics contains Phones and Laptops, Phones contains Android and iOS. You need to list everything under a category, count the leaves, and find how deep the tree goes.
Code #
class TreeNode:
def __init__(self, name):
self.name = name
self.children = []
def add(self, child):
self.children.append(child)
return child
root = TreeNode("Electronics")
phones = root.add(TreeNode("Phones"))
laptops = root.add(TreeNode("Laptops"))
phones.add(TreeNode("Android"))
phones.add(TreeNode("iOS"))
laptops.add(TreeNode("Ultrabooks"))
def height(node):
if not node.children:
return 1 # a leaf is height 1
return 1 + max(height(child) for child in node.children)
def leaves(node):
if not node.children:
return [node.name]
result = []
for child in node.children:
result.extend(leaves(child))
return result
def show(node, depth=0):
print(" " * depth + node.name)
for child in node.children:
show(child, depth + 1)
show(root)
print(height(root)) # 3
print(leaves(root)) # ['Android', 'iOS', 'Ultrabooks']
# Binary tree traversals — the three classic orders
class BinaryNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
tree = BinaryNode(8, BinaryNode(3, BinaryNode(1), BinaryNode(6)), BinaryNode(10))
def in_order(node, out=None): # left, self, right -> sorted for a BST
out = [] if out is None else out
if node:
in_order(node.left, out)
out.append(node.value)
in_order(node.right, out)
return out
def pre_order(node, out=None): # self, left, right -> copying a tree
out = [] if out is None else out
if node:
out.append(node.value)
pre_order(node.left, out)
pre_order(node.right, out)
return out
def post_order(node, out=None): # left, right, self -> deleting, folder sizes
out = [] if out is None else out
if node:
post_order(node.left, out)
post_order(node.right, out)
out.append(node.value)
return out
print(in_order(tree)) # [1, 3, 6, 8, 10]
print(pre_order(tree)) # [8, 3, 1, 6, 10]
print(post_order(tree)) # [1, 6, 3, 10, 8] Electronics depth 0 (root)
/ \
Phones Laptops depth 1
/ \ \
Android iOS Ultrabooks depth 2 (leaves)How it works #
TreeNode holds a value and a list of children. That is all a general tree needs — the structure emerges from how nodes reference each other.
height is recursive because the definition is recursive: the height of a node is one more than the tallest of its children. A leaf hits the base case and returns 1.
leaves collects names from every node with no children, extending the result as it comes back up the recursion.
show prints with indentation proportional to depth, which is how folder listings and category trees are rendered.
The three traversal orders differ only in when the current node is handled relative to its children.
In-order (left, self, right) produces sorted output for a binary search tree, which is the next lesson.
Pre-order (self, left, right) visits a parent before its children — the right order for copying a tree or serialising it, because the parent must exist before the children can be attached.
Post-order (left, right, self) handles children first. That is what you want for deleting a tree, or for calculating folder sizes, since a folder's size depends on its contents being measured first.
Real-world use #
Trees are everywhere: file systems, HTML and the DOM, JSON documents, category hierarchies, comment threads, organisation charts, decision trees in machine learning, and the parse trees compilers build from source code.
Database indexes use B-trees, which are trees with many children per node, chosen because each node maps to a disk page and fewer levels means fewer disk reads.
Choosing a traversal is a real decision. Rendering a nested menu is pre-order. Computing directory sizes is post-order. Listing a sorted view of a BST is in-order.
Storing trees in a relational database is a recurring practical problem, usually solved with a parent_id column plus a recursive query, or with a materialised path like /electronics/phones/android that trades write cost for read simplicity.
Common mistakes #
- Building a cycle by accident, which turns traversal into infinite recursion.
- Deep recursion on an unbalanced tree, hitting the recursion limit — use an explicit stack.
- Choosing the wrong traversal, for example deleting parents before children.
- Confusing depth (distance from the root) with height (distance to the deepest leaf).
- Querying a database once per node when one recursive query would fetch the whole tree.
Practice #
Build a tree representing a folder structure where each leaf has a file size. Write functions for total size (post-order), a printed listing with indentation (pre-order), and the deepest path in the tree. Then rewrite the listing using an explicit stack instead of recursion.