Algorithms 101: Non-Recursive Binary Tree Traversal

Non-Recursive Binary Tree Traversal

by 砖家王二狗

In-order Traversal:
In in-order traversal, we visit the left subtree, then the root, and finally the right subtree. Here’s a non-recursive example in Python:

def in_order_traversal(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

Pre-order Traversal:
In pre-order traversal, we visit the root, then the left subtree, and finally the right subtree. Here’s a non-recursive example in Python:

def pre_order_traversal(root):
    result = []
    stack = [root]
    while stack:
        current = stack.pop()
        if current:
            result.append(current.val)
            stack.append(current.right)
            stack.append(current.left)
    return result

Post-order Traversal:
In post-order traversal, we visit the left subtree, then the right subtree, and finally the root. Here’s a non-recursive example in Python:

def post_order_traversal(root):
    result = []
    stack = [root]
    while stack:
        current = stack.pop()
        if current:
            result.append(current.val)
            stack.append(current.left)
            stack.append(current.right)
    return result[::-1]

These non-recursive implementations use a stack to simulate the recursive process of traversing a binary tree.

Recursive Binary Tree Traversal

In-order Traversal:
In in-order traversal, we visit the left subtree, then the root, and finally the right subtree. This can be achieved using a recursive function. Here’s an example in Python:

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.val)
        in_order_traversal(root.right)

Pre-order Traversal:
In pre-order traversal, we visit the root, then the left subtree, and finally the right subtree. Here’s a recursive example in Python:

def pre_order_traversal(root):
    if root:
        print(root.val)
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

Post-order Traversal:
In post-order traversal, we visit the left subtree, then the right subtree, and finally the root. Here’s a recursive example in Python:

def post_order_traversal(root):
    if root:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.val)

These recursive implementations utilize the inherent nature of binary trees to traverse them in a specific order, making use of the recursive calls to visit each node in the desired sequence.