Python Binary Trees
A binary tree is a data structure made of connected nodes, where each node holds a value and points to at most two children, conventionally called the left and right child. Binary trees underlie many other structures you’ll meet later — binary search trees, heaps, tries, and even the parse trees compilers use — because they let you represent hierarchy and enable fast search, insertion, and ordered traversal. Understanding how to build and walk a binary tree by hand in Python is essential before you reach for a library implementation.
Overview: How Binary Trees Work
Python has no built-in binary tree type — unlike lists or dicts, trees are built out of ordinary objects that reference each other. The standard approach is a small Node (or TreeNode) class with three attributes: the stored value, and two references, left and right, that point to other Node objects or to None when there is no child. A binary tree, then, is really just a graph of these node objects connected by references, with one node designated the root — the entry point from which every other node is reachable.
Internally, each Node instance lives on the heap, and left/right are ordinary Python references, the same kind of reference a variable holds to a list or a string. There’s nothing magical about a tree in memory — it is simply objects pointing to other objects, and the tree shape emerges entirely from how those references are wired up. Because Python passes objects by reference, writing node.left = child does not copy the child node; it points node.left at the exact same object child refers to. This matters when you mutate a shared subtree: any variable referencing that subtree sees the change, since they all point at the same underlying objects.
A binary search tree (BST) is a binary tree with an ordering rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. Nothing about a plain Node class enforces this — your insert logic is what maintains the rule. This ordering is what makes search, insertion, and deletion run in roughly O(log n) time on a balanced tree, versus O(n) for a plain list. A poorly built BST (for example, inserting already-sorted data) degrades into a structure equivalent to a linked list with O(n) operations, which is why self-balancing variants like AVL trees and red-black trees exist for production use.
Trees are naturally recursive structures: the left child of any node is itself the root of a smaller binary tree, and the same is true of the right child. This is why almost every tree algorithm — searching, inserting, computing height, traversing — is written as a recursive function that handles the current node and then delegates to the same function for node.left and node.right. The base case is almost always "the node is None."
Syntax
There is no dedicated tree syntax in Python — you define the shape yourself with a class. The conventional pattern looks like this:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value # the data stored at this node
self.left = left # reference to left child Node, or None
self.right = right # reference to right child Node, or None
| Part | Meaning |
|---|---|
value |
The data stored in the node (any type — int, str, custom object). |
left |
Reference to the left child Node, or None if there isn’t one. |
right |
Reference to the right child Node, or None if there isn’t one. |
| root | The single node from which the whole tree is reached; usually stored in a variable or wrapped in a Tree/BinarySearchTree class. |
You build trees by constructing Node objects and wiring their left/right attributes, either directly for a small fixed tree, or through an insert() method that walks the tree following the BST ordering rule.
Examples
Example 1: Building a Tree Manually
The simplest way to understand a tree is to build one by hand, wiring up Node objects directly:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
# root = 10
# root.left = 5, with children 3 and 7
# root.right = 15, with right child 20
root = Node(10,
Node(5, Node(3), Node(7)),
Node(15, None, Node(20)))
print(root.value)
print(root.left.value, root.right.value)
print(root.left.left.value, root.left.right.value)
print(root.right.right.value)
Output:
10
5 15
3 7
20
Each call to Node(...) creates one object; passing another Node as the left or right argument wires that object in as a child. root.left.left.value walks two references deep — from the root, to its left child (5), to that node’s left child (3) — which is exactly how you will traverse trees in every algorithm that follows.
Example 2: A Binary Search Tree with Insert and Search
A more realistic tree wraps node creation and traversal logic inside a class, so callers never manipulate Node objects directly and the ordering invariant stays intact:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
if self.root is None:
self.root = TreeNode(value)
else:
self._insert(self.root, value)
def _insert(self, node, value):
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
else:
self._insert(node.left, value)
elif value > node.value:
if node.right is None:
node.right = TreeNode(value)
else:
self._insert(node.right, value)
# Duplicate values are ignored
def contains(self, value):
return self._contains(self.root, value)
def _contains(self, node, value):
if node is None:
return False
if value == node.value:
return True
if value < node.value:
return self._contains(node.left, value)
return self._contains(node.right, value)
bst = BinarySearchTree()
for num in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
bst.insert(num)
print(bst.contains(6))
print(bst.contains(9))
print(bst.root.value)
Output:
True
False
8
Inserting [8, 3, 10, 1, 6, 14, 4, 7, 13] one at a time builds a tree rooted at 8, where every left descendant is smaller and every right descendant is larger. contains(6) walks down comparing at each step and finds it; contains(9) walks down and eventually hits a None child, returning False, since 9 was never inserted.
Example 3: Traversals — Inorder, Preorder, Postorder, and Level-order
Once you can build a tree, the next essential skill is visiting every node in a defined order:
from collections import deque
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
return root
def inorder(node, result):
if node is not None:
inorder(node.left, result)
result.append(node.value)
inorder(node.right, result)
def preorder(node, result):
if node is not None:
result.append(node.value)
preorder(node.left, result)
preorder(node.right, result)
def postorder(node, result):
if node is not None:
postorder(node.left, result)
postorder(node.right, result)
result.append(node.value)
def level_order(root):
result = []
if root is None:
return result
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return result
root = None
for num in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
root = insert(root, num)
in_order_result = []
pre_order_result = []
post_order_result = []
inorder(root, in_order_result)
preorder(root, pre_order_result)
postorder(root, post_order_result)
print("Inorder:", in_order_result)
print("Preorder:", pre_order_result)
print("Postorder:", post_order_result)
print("Level-order:", level_order(root))
Output:
Inorder: [1, 3, 4, 6, 7, 8, 10, 13, 14]
Preorder: [8, 3, 1, 6, 4, 7, 10, 14, 13]
Postorder: [1, 4, 7, 6, 3, 13, 14, 10, 8]
Level-order: [8, 3, 10, 1, 6, 14, 4, 7, 13]
Inorder visits left, then the node, then right — on a BST this always produces values in sorted order, which is a handy way to double-check a tree’s ordering invariant. Preorder visits the node before its children, which is useful for copying or serializing a tree. Postorder visits the node after its children, which is useful when you need to process children before their parent (like deleting a whole subtree safely). Level-order ignores the recursive left/right structure entirely and instead visits nodes breadth-first using a deque as a first-in-first-out queue.
How It Works Step by Step (Under the Hood)
Trace what happens when bst.insert(6) runs against a tree that already contains 8 as the root, with 3 as its left child and 1 as 3’s left child:
bst.insert(6)callsself._insert(self.root, 6), sinceself.rootalready exists (value 8).- Inside
_insert, Python evaluates6 < 8— true — so it looks atnode.left. That’s the node holding 3, which is notNone, so it recurses:self._insert(node_3, 6). - Now
6 < 3is false, and6 > 3is true, so Python looks atnode_3.right. It isNone, so a brand-newTreeNode(6)is created and assigned directly tonode_3.right. - The recursion unwinds. No further work happens on the way back up, because each stack frame already made and applied its decision before returning.
- Nothing above node 3 changed; only the single reference
node_3.rightwas updated, because Python passes thenodereference into each call rather than copying the subtree it points to.
This "compare, then recurse left or right" shape underlies almost every BST operation. Search (contains) is identical except it returns a boolean instead of creating a node. Deletion is trickier: removing a node with two children requires finding its in-order successor (the smallest value in its right subtree) to replace it — beyond this lesson’s scope, but worth knowing it exists before you reach for it.
Traversals work the same recursive way, just visiting the node’s value at a different point relative to the two recursive calls: before both (preorder), between them (inorder), or after both (postorder). Level-order traversal is the exception — it is iterative rather than recursive, because it needs a queue to visit nodes breadth-first, one depth level at a time, instead of diving all the way down one branch first.
Common Mistakes
Mistake 1: Forgetting to check for None before touching a node’s attributes. This raises an AttributeError the moment recursion reaches an empty spot in the tree:
def insert(node, value):
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
This crashes with AttributeError: 'NoneType' object has no attribute 'value' as soon as node is None — which happens on the very first insert into an empty tree, since the function never checks whether node itself is empty before reading node.value. The fix is to handle the empty case first:
def insert(node, value):
if node is None:
return TreeNode(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
Mistake 2: Discarding the recursive call’s return value. Recursive insert functions typically return the (possibly newly created) subtree root, and the caller must reassign it — skipping that step silently loses data:
def insert(node, value):
if node is None:
return TreeNode(value)
if value < node.value:
insert(node.left, value)
else:
insert(node.right, value)
return node
When node.left is None, insert(node.left, value) creates a brand-new TreeNode and returns it — but that return value is thrown away because the line never assigns it back to node.left. The new node is built and then immediately garbage-collected, and the value silently vanishes from the tree with no error at all. The corrected version reassigns the result:
def insert(node, value):
if node is None:
return TreeNode(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
Best Practices
- Wrap node creation and traversal logic inside a class (like
BinarySearchTree) instead of exposing rawNodeobjects, so callers can’t accidentally break the ordering invariant. - Always check
if node is Noneas the very first line of a recursive tree helper, before reading any attribute offnode. - Reassign the result of recursive insert/delete calls back to
node.left/node.right— these functions return the (possibly new) subtree root, and dropping that return value silently loses nodes. - Prefer an iterative traversal with an explicit stack or
dequeover deep recursion when a tree might be very large or unbalanced, since Python’s default recursion limit (around 1000 frames) raisesRecursionErroron a deeply skewed tree. - Use
collections.dequerather than a plain list for breadth-first/level-order queues —deque.popleft()isO(1), whilelist.pop(0)isO(n). - Keep shape-mutating operations (insert, delete) and read-only operations (search, traverse) as clearly separate methods, rather than mixing side effects into a traversal.
- If insertion order is unpredictable or adversarial, a plain BST can degrade to
O(n)per operation; consider a self-balancing tree or a library structure (such as theheapqmodule or the third-partysortedcontainerspackage) for production use.
Practice Exercises
- Write a function
height(node)that returns the height of a binary tree (the number of edges on the longest path from the node down to a leaf, with an empty tree having height-1). Test it against the tree built in Example 3. - Write a function
count_nodes(node)that returns the total number of nodes in a tree, using the same recursive "handle this node, then delegate to left and right" pattern shown in this lesson. - Write a function
is_valid_bst(node)that checks whether a tree actually satisfies the binary-search-tree ordering property. Hint: comparing a node only to its immediate children isn’t enough — track an allowed(low, high)range as you recurse, narrowing it each time you go left or right.
Summary
- A binary tree is built from node objects linked via
left/rightreferences; Python has no built-in tree type. - A binary search tree adds an ordering rule (left < node < right) that enables roughly
O(log n)search and insert on a balanced tree, but degrades towardO(n)if the tree becomes unbalanced. - Inorder, preorder, and postorder traversals are recursive and differ only in when the current node’s value is visited relative to the two recursive calls; inorder on a BST yields values in sorted order.
- Level-order (breadth-first) traversal is iterative and uses a queue, typically
collections.deque, rather than recursion. - Always check for
Nonebefore dereferencing a node, and always reassign a recursive call’s return value back into the parent’sleft/rightattribute. - For very large, unbalanced, or production-grade use cases, prefer a self-balancing tree or an existing library structure over a hand-rolled BST.
