PYTHON / DATA STRUCTURES AND ALGORITHMS
Trees and binary trees
Model trees with a node class, traverse a binary tree four ways, compute its height, and explain why shape rather than node count decides cost.
What you will learn
- Build a binary tree from a Node class by nesting constructors
- Write tree recursion with `if node is None` as the base case
- Produce preorder, inorder, postorder and level-order from one tree
- Explain why height, not node count, bounds traversal stack space
Understanding Trees and binary trees
A tree is a set of nodes where each node holds a value plus links to its children, and there is exactly one path from the root down to any node. That uniqueness is what separates a tree from a general graph: no cycles and no node with two parents, so a downward walk can never revisit anything and needs no visited set. Python ships list and dict as builtins but has no tree type, so you write a small Node class yourself and the shape lives entirely in the references between instances.
A binary tree restricts each node to at most two children, and left and right are distinct positions rather than just the first two entries of a list. The definition is recursive: a binary tree is either None, or a node whose left and right are themselves binary trees. That is why nearly every tree function has the same skeleton, handle None, then combine the answers from left and right, and why forgetting the None branch is the single most common crash. Note that height depends on a convention: returning -1 for None counts edges, returning 0 counts nodes.
The three depth-first orders differ only in where you record the node relative to the two recursive calls: before them is preorder, between them is inorder, after them is postorder. Preorder sees a parent before its children, which suits copying and serializing; postorder sees children first, which suits deleting a subtree, summing sizes, or evaluating an expression tree. Level order cannot use the call stack at all, so you drive it with a queue. All four are O(n) time, but the recursive ones use stack space proportional to the height, and n nodes can mean a height near log2 n when balanced or n-1 when the tree degenerates into a chain.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
# A
# / \
# B C
# / \ \
# D E F
tree = Node("A",
Node("B", Node("D"), Node("E")),
Node("C", None, Node("F")))
def preorder(node, out):
if node is None:
return
out.append(node.value)
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.value)
inorder(node.right, out)
def postorder(node, out):
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(node.value)
def level_order(root):
out, queue = [], deque([root])
while queue:
node = queue.popleft()
out.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return out
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
for name, walk in (("preorder", preorder), ("inorder", inorder), ("postorder", postorder)):
out = []
walk(tree, out)
print(f"{name:<10}{out}")
print(f"{'level':<10}{level_order(tree)}")
print(f"{'height':<10}{height(tree)}")
A binary tree is defined recursively as None or a node with two subtrees, so the natural way to compute anything about it is a function that calls itself on left and right.
Worked examples
Preorder without recursion
Replaces the call stack with an explicit list so a 20000-deep left chain does not blow up.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6)))
def preorder_iterative(root):
order, stack = [], [root]
while stack:
node = stack.pop()
order.append(node.value)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return order
print(preorder_iterative(root))
chain = Node(0)
for i in range(1, 20000):
chain = Node(i, chain)
print(len(preorder_iterative(chain)))
Example explained
Line 1stack.pop() removes the most recently pushed node, so the stack replays the order of recursive calls.
Line 2The right child is pushed before the left child precisely so the left child comes off first, matching preorder.
Line 3chain is 20000 nodes deep with only left links; a recursive version would raise RecursionError well before that.
Line 4Both versions do the same O(n) work; only the storage for pending nodes moves from the interpreter's frames to a heap list.
A tree that is not binary
Shows the same recursion pattern on nodes with an arbitrary number of children.
project = {
"name": "project",
"children": [
{"name": "main.py", "size": 120, "children": []},
{"name": "pkg", "children": [
{"name": "a.py", "size": 40, "children": []},
{"name": "b.py", "size": 60, "children": []},
]},
],
}
def total_size(node):
return node.get("size", 0) + sum(total_size(c) for c in node["children"])
def depth(node):
if not node["children"]:
return 1
return 1 + max(depth(c) for c in node["children"])
print(total_size(project))
print(depth(project))
Example explained
Line 1node.get("size", 0) defaults to 0 because directory nodes carry no size of their own.
Line 2sum over node["children"] generalises the fixed left/right pair to any number of children.
Line 3The base case here is a leaf with an empty children list, not None, because a dict node always exists.
Line 4depth counts nodes on the longest root-to-leaf path, so a single leaf has depth 1, not 0.
Leaves versus internal nodes
Demonstrates that leaves = internal + 1 holds only when every node has exactly 0 or 2 children.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def counts(node):
if node is None:
return 0, 0
if node.left is None and node.right is None:
return 1, 0
left_leaves, left_internal = counts(node.left)
right_leaves, right_internal = counts(node.right)
return left_leaves + right_leaves, left_internal + right_internal + 1
full = Node(1, Node(2, Node(4), Node(5)), Node(3))
lopsided = Node(1, Node(2, Node(4)), Node(3))
for name, tree in (("full", full), ("lopsided", lopsided)):
leaves, internal = counts(tree)
print(name, leaves, internal, leaves == internal + 1)
Example explained
Line 1counts returns a pair, so one traversal collects two answers instead of walking the tree twice.
Line 2The leaf test needs both children to be None; checking only node.left would miscount a node with just a right child.
Line 3In `full` every internal node has two children, so the identity leaves == internal + 1 holds.
Line 4`lopsided` has one node with a single child, which adds an internal node without adding a leaf, breaking the identity.
Important notes
Reusing one Node object as a child in two places is no longer a tree: the traversal visits it twice and any size or sum computation double counts it.
Raising sys.setrecursionlimit does not add C stack space, so a very deep recursion can hard-crash the interpreter instead of raising; use an explicit stack for deep trees.
Common mistakes
Omitting the None base case and recursing straight into node.left.value, which raises AttributeError: 'NoneType' object has no attribute 'value' on the first leaf.
Assuming n nodes implies height about log2 n; a tree built by repeatedly attaching to one side is a chain, and recursing on 100000 such nodes raises RecursionError at CPython's default limit of 1000 frames.
Expecting inorder to print values in sorted order for any binary tree; sortedness comes from the search-tree ordering rule, and an arbitrary tree like the one above yields D B E A C F.
Try it yourself
Change, predict, then run
Build the tree from the main example, then write mirror(node) that recursively swaps left and right in place, and print the preorder before and after to confirm you get A B D E C F and then A C F B E D.
Open the Python workspaceCheck your understanding
A binary tree of 100000 nodes forms a single left-going chain. Recursive postorder raises RecursionError, but the same traversal with an explicit list as a stack finishes. Why?
- Recursion needs one interpreter frame per level and the tree is 100000 levels deep, while the iterative version keeps pending nodes in a heap-allocated list that can grow freely.
- The iterative version visits fewer nodes because it skips None children that recursion still descends into.
- Postorder is inherently more expensive than preorder, so only preorder can safely be written recursively.
- A chain is not a valid binary tree, so recursive traversal detects the malformed shape and refuses to continue.
Show answer
Both versions do identical O(n) work; the only difference is where the pending nodes live. CPython caps call depth (1000 by default) but a list on the heap is limited only by memory. Option 2 is tempting because recursion does make calls with None, but those calls return immediately and both versions still record exactly n nodes, so the visit count is the same.