Binary Tree
Learn the structure of a binary tree and how to build one from scratch in Python.
Binary Tree
A binary tree is a tree where every node has at most two children, conventionally called left and right. There is no ordering requirement — a node's value can be anything relative to its children. That ordering rule is what makes a binary search tree a separate, more specific structure.
The node
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = NoneBuilding a tree manually
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(20)
# 10
# / \
# 5 15
# / \ \
# 3 7 20Types of binary trees
| Type | Rule |
|---|---|
| Full | Every node has 0 or 2 children — never exactly 1 |
| Complete | Every level is fully filled except possibly the last, which fills left to right |
| Perfect | Every level is completely filled — leaf count = 2^height |
| Balanced | Height difference between left and right subtrees is at most 1, for every node |
| Degenerate | Every node has only one child — essentially a linked list |
Full: Complete: Perfect: Degenerate:
1 1 1 1
/ \ / \ / \ \
2 3 2 3 2 3 2
/ \ / \ / \
4 5 4 5 6 3Basic operations
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def height(node):
"""Height of the tree — longest path from node to a leaf."""
if node is None:
return -1 # empty tree has height -1, single node has height 0
return 1 + max(height(node.left), height(node.right))
def count_nodes(node):
"""Total number of nodes in the tree."""
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
def count_leaves(node):
"""Count nodes with no children."""
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return count_leaves(node.left) + count_leaves(node.right)
def is_balanced(node):
"""Check if every subtree has height difference <= 1."""
def check(node):
if node is None:
return 0, True
left_height, left_balanced = check(node.left)
right_height, right_balanced = check(node.right)
balanced = (
left_balanced and right_balanced
and abs(left_height - right_height) <= 1
)
return 1 + max(left_height, right_height), balanced
_, balanced = check(node)
return balancedWhy recursion fits trees naturally
Every tree operation has the same shape — handle the current node, then recurse on left and right. This mirrors the tree's own recursive definition: a tree is a node with two subtrees, each of which is also a tree.
def process(node):
if node is None:
return base_case_value
# do something with node.value
left_result = process(node.left)
right_result = process(node.right)
# combine results
return combined_resultAlmost every tree algorithm follows this template: base case for None, do work at the current node, recurse left, recurse right, combine results. Once this pattern feels natural, most tree problems become a matter of figuring out what "do work" and "combine" mean for that specific problem.
Complexity
| Operation | Time | Space (call stack) |
|---|---|---|
| Height | O(n) | O(h) |
| Count nodes | O(n) | O(h) |
| Count leaves | O(n) | O(h) |
| Check balanced | O(n) | O(h) |
Where n is the number of nodes and h is the height of the tree. For a balanced tree, h = O(log n). For a degenerate tree, h = O(n).