Binary Tree in Python: Traversals Explained

A binary tree is a structure where every item, called a node, has at most two children: a left child and a right child. It grows downward from a single starting node, the root. Trees model anything hierarchical: folders on a disk, a family tree, the structure of an HTML page, or the decisions in an algorithm.

This guide builds a tree in Python and explains the four ways of visiting every node (preorder, inorder, postorder and level-order), then uses recursion to measure a tree and solve common interview problems. All the output shown is real.

Tree vocabulary

Building a binary tree

Python has no built-in tree, so you define a small node class, like the one in Linked List in Python, but with two links instead of one. We will use this tree for the rest of the post:

        1
       / \
      2   3
     / \   \
    4   5   6

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, None, TreeNode(6)))

print(tree.value, tree.left.value, tree.right.value)
print(tree.left.left.value, tree.left.right.value)
print(tree.right.left)

Output

1 2 3
4 5
None

Nodes 4, 5 and 6 are leaves. Node 3 has only a right child, which is fine: a missing child is simply None.

Depth-first traversals

Depth-first means going as deep as possible before moving sideways. The three orders differ in one thing: when you handle the node, relative to its two subtrees. The code is almost identical. Only the position of yield node.value moves. (These are generators that use yield from, see Python Iterators and Generators.)

def preorder(node):
    if node:
        yield node.value
        yield from preorder(node.left)
        yield from preorder(node.right)

def inorder(node):
    if node:
        yield from inorder(node.left)
        yield node.value
        yield from inorder(node.right)

def postorder(node):
    if node:
        yield from postorder(node.left)
        yield from postorder(node.right)
        yield node.value

print("preorder :", list(preorder(tree)))
print("inorder  :", list(inorder(tree)))
print("postorder:", list(postorder(tree)))

Output

preorder : [1, 2, 4, 5, 3, 6]
inorder  : [4, 2, 5, 1, 3, 6]
postorder: [4, 5, 2, 6, 3, 1]

Follow the inorder result: 4 2 5 1 3 6. Everything in the left subtree (4, 2, 5) comes first, then the root 1, then the right subtree (3, 6). That property is what makes inorder useful for the next post, Binary Search Tree in Python From Scratch. All three visit each node once, so they are O(n).

Level-order traversal (BFS)

Level-order visits the tree row by row: the root, then its children, then their children. Recursion is the wrong tool here, and a queue is the right one. Take a node from the front of the queue and put its children at the back. The inner for loop runs for exactly the number of nodes in the current level, which lets us collect one list per level:

from collections import deque

def level_order(root):
    result = []
    queue = deque([root]) if root else deque()
    while queue:
        level = []
        for _ in range(len(queue)):          # exactly one level per pass
            node = queue.popleft()
            level.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

print(level_order(tree))
print(level_order(None))

Output

[[1], [2, 3], [4, 5, 6]]
[]

This is breadth-first search, the same idea used for graphs in Graphs in Python: Adjacency List, BFS and DFS. It uses deque from Queue and Deque in Python Explained, because list.pop(0) would be slow.

Traversals without recursion

Recursion uses Python’s call stack behind the scenes. You can use your own stack instead, which avoids recursion limits and is a favourite interview follow-up (Stack in Python explains the tool). Preorder is the easy one: pop a node, record it, push the right child, then the left, so that the left one comes off first. Inorder goes as far left as it can, records the node when it comes back, and then turns right:

def inorder_iter(root):
    out, stack, node = [], [], root
    while node or stack:
        while node:                  # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.value)
        node = node.right
    return out

def preorder_iter(root):
    out = []
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.value)
        if node.right:               # right first, so left is popped first
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

print(inorder_iter(tree))
print(preorder_iter(tree))

Output

[4, 2, 5, 1, 3, 6]
[1, 2, 4, 5, 3, 6]

Height, size and leaves

Here is the pattern that solves most tree problems. First, decide what to return for an empty tree (None). Then, trust the function to work on the left and right subtrees, and combine their answers with the current node:

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

def count_leaves(node):
    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)

print("height :", height(tree))
print("nodes  :", count_nodes(tree))
print("leaves :", count_leaves(tree))
print("empty  :", height(None), count_nodes(None))

Output

height : 3
nodes  : 6
leaves : 3
empty  : 0 0

Height: a tree is one node taller than its taller child. Count: one for this node plus both subtrees. Leaves: a node with no children counts as one. You never have to think about the whole tree at once. (Recursion has its own guide: Recursion in Python Explained Simply.)

Two classic problems

Invert a binary tree swaps the left and right child of every node. It is a good example of recursion doing all the work. The inverted tree is a mirror image, so in preorder we now meet 3 before 2:

def preorder(node):
    if node:
        yield node.value
        yield from preorder(node.left)
        yield from preorder(node.right)

def invert(node):
    if node:
        node.left, node.right = invert(node.right), invert(node.left)
    return node

print(list(preorder(tree)))
invert(tree)
print(list(preorder(tree)))

Output

[1, 2, 4, 5, 3, 6]
[1, 3, 6, 2, 5, 4]

Path sum asks: is there a path from the root down to a leaf whose values add up to a target? Subtract the current value as you go down, and check at each leaf whether what is left is exactly that leaf’s value. The three root-to-leaf paths here add up to 7, 8 and 10:

def has_path_sum(node, target):
    if node is None:
        return False
    if node.left is None and node.right is None:
        return node.value == target
    rest = target - node.value
    return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)

for target in [7, 8, 9, 10]:
    print(target, has_path_sum(tree, target))

Output

7 True
8 True
9 False
10 True

Kinds of binary trees

Shape matters because the height sets the cost of many operations. A balanced tree with a million nodes is only about 20 levels tall, but a skewed one is a million levels tall. A tree with only a left child on every node is easy to build, and it shows a limit of recursion:

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

root = None
for i in range(5000):                 # every node has only a left child
    root = TreeNode(i, left=root)

try:
    height(root)
except RecursionError as e:
    print(type(e).__name__)

Output

RecursionError

Python stops recursion at roughly a thousand levels by default. The iterative versions above do not have that limit, which is one reason to know them.

Complexity

Every node is visited once, so time is O(n). The extra space is the height h: about log n for a balanced tree and up to n for a skewed one. If you need fast search, an ordinary binary tree is not enough, and that is what binary search trees are for.

Common mistakes

• Missing the base case. Always start with if node is None. Without it, the code fails on None.
• Mixing up depth and height. Depth counts down from the root to a node. Height counts down from a node to its deepest leaf. Also check whether the problem counts nodes or edges.
• Calling the wrong order. Read the required order carefully. Inorder on a plain binary tree is not sorted.
• Checking the leaf too early or too late. A leaf has both children missing. A node with one child is not a leaf, as node 3 shows.
• Forgetting to return. In recursive helpers, returning nothing gives None, which then breaks the + or max above it.
• Confusing a binary tree with a binary search tree. Only the second one keeps its values ordered.

Try it yourself

Work out each answer first, then open the solution. The tree from above is assumed.

1. Write tree_sum that adds up every value in the tree.

def tree_sum(node):
    if node is None:
        return 0
    return node.value + tree_sum(node.left) + tree_sum(node.right)

print(tree_sum(tree))

21

2. List the leaf values from left to right.

def leaves(node):
    if node:
        if not node.left and not node.right:
            yield node.value
        yield from leaves(node.left)
        yield from leaves(node.right)

print(list(leaves(tree)))

[4, 5, 6]

3. Write contains(node, target) that says whether a value is in the tree.

def contains(node, target):
    if node is None:
        return False
    return (node.value == target
            or contains(node.left, target)
            or contains(node.right, target))

print(contains(tree, 5), contains(tree, 9))

True False

4. Which traversal visits a node before its children, and which one would you use to read a binary search tree in sorted order?

Run these in our free Python compiler.

Frequently asked questions

What is a binary tree in Python?

A binary tree is a structure of nodes where each node has at most two children, called left and right. Python has no built-in one, so you create a TreeNode class with value, left and right.

What are the types of binary tree traversal?

Depth-first traversals (preorder, inorder and postorder) and breadth-first traversal (level-order). They differ in the order in which the nodes are visited.

What is the difference between inorder, preorder and postorder?

They differ in when the current node is handled. Preorder: node, left, right. Inorder: left, node, right. Postorder: left, right, node.

How do you find the height of a binary tree in Python?

Use recursion: the height of an empty tree is 0, and the height of any other node is 1 plus the larger of its two children’s heights.

What is the difference between a binary tree and a binary search tree?

A binary tree only limits each node to two children. A binary search tree also keeps values ordered: everything on the left is smaller, everything on the right is larger, which allows fast search.

What is the time complexity of tree traversal?

O(n), since every node is visited once. The extra memory is O(h) for the recursion, where h is the height of the tree.

Related reading

• Binary Search Tree in Python From Scratch – a tree that keeps its values ordered.
• Recursion in Python Explained Simply – the technique behind every tree function.
• Graphs in Python: Adjacency List, BFS and DFS – trees are graphs without cycles.
• Queue and Deque in Python Explained – the tool behind level-order.