Inorder Traversal of a tree both using recursion and Iteration

The problem, simply

You get a binary tree. Write down every value in this order: first everything in the left side, then the node itself, then everything in the right side. Do the same inside each side. This order is called inorder.

You must do it two ways: with a function that calls itself, and with a loop and your own stack.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write a helper that reads one node: first it reads the left side with itself, then writes the node, then reads the right side with itself. An empty node does nothing.

1. If the node is empty, return.
2. Read the left side.
3. Write the node's value.
4. Read the right side.

import java.util.*;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        read(root, out);
        return out;
    }

    private void read(TreeNode node, List<Integer> out) {
        if (node == null) return;
        read(node.left, out);     // left family first
        out.add(node.val);        // then me
        read(node.right, out);    // then right family
    }
}

How long it takes: each node is written once, O(n). Extra room: the waiting helpers form a pile as tall as the tree, O(h). That is O(n) for a stick.

Way 2: the clever way

Do the same thing with your own pile of bookmarks, a stack. You control it, so a very deep tree cannot crash your program the way deep recursion can, and interviewers love to see it.

1. Start with curr at the root.
2. While curr is not empty, push it on the stack and move curr to its left child. This slides down the left edge.
3. When curr is empty, pop the top bookmark. Write its value.
4. Move curr to that node's right child and go back to step 2.
5. Stop when curr is empty and the stack is empty.

import java.util.*;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {          // slide down the left edge
                stack.push(curr);           // leave a bookmark
                curr = curr.left;
            }
            curr = stack.pop();             // nearest bookmark
            out.add(curr.val);              // write it
            curr = curr.right;              // then its right family
        }
        return out;
    }
}

How long it takes: every node is pushed once and popped once, O(n). Extra room: the stack holds one bookmark per floor on the current way down, O(h).

Way 3: no stack at all (Morris)

Can you do it with O(1) extra room? Yes, by borrowing empty arrows in the tree. Before going into a left family, find the last person that family would write (go left once, then right as far as you can). That person's right arrow is empty. Tie a ribbon from it back to the current node. Later, when the walk follows that ribbon, you know the left family is finished: untie it, write the node, and go right.

import java.util.*;

class Solution {
    public List<Integer> inorderMorris(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                out.add(curr.val);              // nothing on the left: write me
                curr = curr.right;              // may follow a ribbon up
            } else {
                TreeNode pre = curr.left;       // last one written before me
                while (pre.right != null && pre.right != curr) pre = pre.right;
                if (pre.right == null) {
                    pre.right = curr;           // tie the ribbon
                    curr = curr.left;
                } else {
                    pre.right = null;           // untie it, the left side is done
                    out.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return out;
    }
}

Each arrow is walked at most a few times, so it is still O(n) time, with O(1) extra room. The tree is changed during the walk and put back by the end, so it is not safe if another thread reads the tree at the same time.

Watch out for

• Pushing children like in preorder (right, then left) does not give inorder. Inorder needs the "slide left" inner loop.
• An empty tree. The loop never runs and you return an empty list, which is correct.
• In Morris, forgetting to untie the ribbon leaves a loop in the tree.

What interviewers ask next

• Check if a tree is a valid binary search tree. Do an inorder walk and make sure every value is bigger than the one before.
• Find the k-th smallest value in a search tree. Do the iterative inorder walk and stop at the k-th pop.
• Build a search tree iterator with next() and hasNext(). Keep the stack between calls: next() pops one node and slides left from its right child. Each call is O(1) on average and memory is O(h).
• Recover a search tree where two values were swapped. Inorder finds the two places where the order goes down.

Remember this

Grown-up words: the bookmarks are a stack, the helper that calls itself is recursion, the waiting helpers are the call stack, the ribbons are threads (Morris traversal uses a threaded binary tree), and the last person in a left family is the inorder predecessor.