Iterative In-Order Traversal

Problem

Return the values of a binary tree using in-order traversal, iteratively.

Input

• node: Has 3 properties
  • .val: Integer value of the node
  • .left: A pointer to another node object, or None if null
  • .right: A pointer to another node object, or None if null

Approach

The recursive approach is simple. Since in-order traversal has a LNR pattern (Left - Node - Right), we can retrieve the results by having the following:

        def _inorder(root):
            if root == None:
                return

            _inorder(root.left)
            results.append(root.val)
            _inorder(root.right)

        _inorder(root)

The recursive approach internally takes advantage of the fact that recursive calls are stored into a stack - or the call stack. Thus, when thinking about the iterative approach, we should simply use a stack data structure. A list does the trick here.

Even with a list however, it is still a bit tricky to represent recursive logic in an iterative fashion. The key intuition here is to only use the stack to remember things that the iterative code really needs. When we traverse down a node's children, we are essentially going through a one-way street. This means that any knowledge of the children's parent is lost. Therefore, we should use a stack to store the parent nodes.

Since in-order traversal is LNR, we want to traverse to the left as far as we can until we could no longer do so. We should store the parent nodes into the stack as we traverse down to the left child. When we reach None or null, we should pop from our stack to retrieve the most recent parent and record that parent's value. Afterwards we should traverse down to the right child and repeat the previous logic for that child.

Solution

    def inorder_traversal(self, root):
        stack = []
        results = []

        while root or stack:
            while root:
                stack.append(root)
                root = root.left

            root = stack.pop()
            results.append(root.val)
            root = root.right

        return results