Preorder Traversal of a tree both using recursion and Iteration

The problem, simply

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

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: write the node, then read the left side with itself, then the right side with itself.

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

import java.util.*;

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

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

How long it takes: each node once, O(n). Extra room: the call stack, as tall as the tree, O(h).

Way 2: the clever way

Use the tour guide's pile of cards, a stack. A stack gives back the last thing you put in, so push the right child first and the left child second. Then the left child is on top and is handled first.

1. Push the root.
2. Pop the top node and write it.
3. Push its right child, then its left child (skip empty ones).
4. Repeat until the stack is empty.

import java.util.*;

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            out.add(node.val);                            // write me
            if (node.right != null) stack.push(node.right);   // right waits below
            if (node.left != null) stack.push(node.left);     // left on top, done next
        }
        return out;
    }
}

How long it takes: each node is pushed and popped once, O(n). Extra room: the stack. It holds at most one waiting right child per floor, plus the card on top, so O(h).

Way 3: no stack at all (Morris)

Like Morris inorder, borrow the empty right arrow of the last node in each left family as a ribbon back up. The only difference: write the node the first time you reach it (when you tie the ribbon), not the second time.

import java.util.*;

class Solution {
    public List<Integer> preorderMorris(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                out.add(curr.val);
                curr = curr.right;
            } else {
                TreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) pre = pre.right;
                if (pre.right == null) {
                    out.add(curr.val);      // first visit: write now
                    pre.right = curr;       // tie the ribbon
                    curr = curr.left;
                } else {
                    pre.right = null;       // second visit: untie and go right
                    curr = curr.right;
                }
            }
        }
        return out;
    }
}

It runs in O(n) time with O(1) extra room, and the tree is back to normal at the end.

Watch out for

• An empty root. Check it before pushing, or you will push null and crash on node.val.
• Using a queue instead of a stack gives level order, not preorder.
• Stack in Java works but is old and slow. ArrayDeque with push and pop is the usual choice.

What interviewers ask next

• Copy a tree, or save it to a string and load it back. Preorder with markers for empty children is the classic way, because the parent comes before its children.
• Flatten a tree into a linked list in preorder. Use the same stack loop and link each popped node to the next one.
• Get postorder from this code. Push left then right to get "me, right, left", then reverse the answer. That gives "left, right, me".
• Build a tree back from its preorder and inorder readings. The first preorder value is the root, and inorder tells you which values are on its left.

Remember this

Grown-up words: the pile of cards is a stack, last in is first out (LIFO), the helper that calls itself is recursion, and the ribbon version is Morris traversal using threads.