Preorder, inorder, and postorder

What is a binary tree?

A tree connects nodes in a hierarchy. The root is its starting node. A child is directly below its parent; a leaf has no children. A binary tree allows at most two children per node, called left and right. Traversal means visiting its nodes in a defined order.

Example: A root containing 8 can have a left child 4 and a right child 12. A binary tree does not automatically keep smaller values on the left: that extra rule belongs to a binary search tree.

Helpful before this chapter

If these ideas are new, begin with:

Queues and deques Recursion

Understand the idea

Traversal order depends on when a node is processed relative to its children. Preorder is node-left-right; inorder left-node-right; postorder left-right-node. Each supports different computations.

Work through an example

The lab tree gives preorder [4,2,1,3,6], inorder [1,2,3,4,6], postorder [1,3,2,6,4]. Only search-tree inorder is necessarily sorted.

Time and space complexity

O(n) visits/O(h) stack; the lab's list-concatenating inorder can take O(n²) time on a chain.

Why it works

Every node is visited once in the chosen order.

Common mistakes

Returning concatenated lists hides copying work.
Do not assume inorder is sorted for arbitrary trees.

Chapter lab · Python implementation

A tree gives each non-root node one parent and contains no cycles. Our binary-tree lab combines inorder traversal, subtree height, and explicit-null serialization. Height counts edges here: empty=-1, leaf=0. Some practice problems count nodes instead; translate the convention rather than changing the recurrence blindly.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def inorder(node):
    if node is None: return []
    return inorder(node.left)+[node.value]+inorder(node.right)

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

def serialize(node):
    tokens=[]
    def visit(n):
        if n is None:
            tokens.append(None); return
        tokens.append(n.value)
        visit(n.left); visit(n.right)
    visit(node)
    return tokens

def deserialize(tokens):
    stream=iter(tokens)
    def build():
        value=next(stream)
        if value is None: return None
        return Node(value,build(),build())
    root=build()
    sentinel=object()
    if next(stream,sentinel) is not sentinel:
        raise ValueError('extra tokens')
    return root

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

root=Node(4,Node(2,Node(1),Node(3)),Node(6))
assert inorder(root)==[1,2,3,4,6]
assert height(root)==2 and height(None)==-1
assert serialize(deserialize(serialize(root)))==serialize(root)
assert serialize(None)==[None]

CHECK YOUR UNDERSTANDING