Editor

Binary tree traversal in Python

A traversal visits every node of a binary tree once. Pre-order, in-order and post-order all walk the same path down the tree; they differ only in when each node is written down.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. walk calls itself on the left subtree, then on the right subtree. An empty branch (None) returns at once.
  2. Pre-order writes the node down before visiting its subtrees, so the root comes first: 4, 2, 1, 3, 6, 5, 7.
  3. In-order writes it between the two subtrees. In a binary search tree that gives the values in sorted order: 1 to 7.
  4. Post-order writes it after both subtrees, so the root comes last. That is the order to delete a tree or add up its sizes.

What to watch

  • Watch node move down the left edge first in every order: 4, then 2, then 1.
  • Watch the call stack: it is never deeper than the tree is tall, plus one call for an empty branch.
  • Watch out grow: the same path down the tree gives three different lists.

The code

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

def walk(node, order, out):
    if node is None:
        return
    if order == "pre":
        out.append(node.value)       # before both subtrees
    walk(node.left, order, out)
    if order == "in":
        out.append(node.value)       # between them
    walk(node.right, order, out)
    if order == "post":
        out.append(node.value)       # after both

root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
for order in ["pre", "in", "post"]:
    out = []
    walk(root, order, out)
    print(order + "-order:", out)
Output
pre-order: [4, 2, 1, 3, 6, 5, 7]
in-order: [1, 2, 3, 4, 5, 6, 7]
post-order: [1, 3, 2, 5, 7, 6, 4]

Open it in the editor · Python Program to Implement a Binary Search Tree, explained