Inorder traversal constant space

Given a binary tree with parent node pointers, implement an inorder traversal using constant space.

Solution

• Use the parent pointer to navigate from child to parent and testing which node must be processed next

Code

def in_order_traversal(root)
    return if root.nil?

    curr = root
    prev = nil
    next = nil

    while !curr.nil?
        # Came down from parent
        if curr.parent = prev

            # Go left if possible
            if !curr.left.nil?
                next = curr.left

            # Go up to parent
            else
                puts curr.data
                next = curr.parent
            end

        # Came up from child
        elsif curr.left = prev
            puts curr.data
            next = curr.right if !curr.right.nil?

        # Done printing both children
        else
            curr = curr.parent
        end

        prev = curr
        curr = next
    end
end

Complexity

• O(n) to traverse the entire tree in order
• O(1) to store temp variables like curr, prev and next