Tree Traversals

Problem Statement

Given the root of a binary tree, traverse it in different orders: inorder, preorder, and postorder.

Example:

       1
      / \
     2   3
    / \
   4   5

Inorder → [4,2,5,1,3]
Preorder → [1,2,4,5,3]
Postorder → [4,5,2,3,1]

Approach 1: Recursive Traversal

Explanation: Use standard recursion for inorder, preorder, and postorder.

Time Complexity: O(n)

Space Complexity: O(h) for recursion stack, where h is tree height

// Inorder
inorder(node):
    if node == NULL: return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

// Preorder
preorder(node):
    if node == NULL: return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

// Postorder
postorder(node):
    if node == NULL: return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

Approach 2: Iterative Using Stack

Explanation: Use a stack to simulate recursion for inorder, preorder, or postorder traversal.

Time Complexity: O(n)

Space Complexity: O(h)

// Iterative Inorder
stack = empty
curr = root
while curr != NULL or stack not empty:
    while curr != NULL:
        stack.push(curr)
        curr = curr.left
    curr = stack.pop()
    print(curr.val)
    curr = curr.right

Approach 3: Morris Traversal (Inorder, O(1) space)

Explanation: Threaded binary tree technique to traverse without recursion or stack.

Time Complexity: O(n)

Space Complexity: O(1)

curr = root
while curr != NULL:
    if curr.left == NULL:
        print(curr.val)
        curr = curr.right
    else:
        predecessor = curr.left
        while predecessor.right != NULL and predecessor.right != curr:
            predecessor = predecessor.right
        if predecessor.right == NULL:
            predecessor.right = curr
            curr = curr.left
        else:
            predecessor.right = NULL
            print(curr.val)
            curr = curr.right