Binary Tree Traversal in Data Structure

Traversal refers to visiting every node of a binary tree exactly once in a specific order. There are four common traversal techniques: Inorder, Preorder, Postorder, and Level Order.

Inorder Traversal (Left, Root, Right)

Visits the left subtree, then the root, then the right subtree. For a Binary Search Tree, inorder traversal produces values in sorted order.

def inorder(node, result=None):
    if result is None:
        result = []
    if node:
        inorder(node.left, result)
        result.append(node.val)
        inorder(node.right, result)
    return result

Preorder Traversal (Root, Left, Right)

Visits the root first, then the left subtree, then the right subtree. Useful for creating a copy of the tree.

def preorder(node, result=None):
    if result is None:
        result = []
    if node:
        result.append(node.val)
        preorder(node.left, result)
        preorder(node.right, result)
    return result

Postorder Traversal (Left, Right, Root)

Visits the left subtree, then the right subtree, then the root. Useful for deleting a tree or evaluating expression trees.

def postorder(node, result=None):
    if result is None:
        result = []
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.val)
    return result

Level Order Traversal (Breadth First)

Visits nodes level by level, using a queue.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

Complexity