Reference: LeetCode
Difficulty: Medium

## Problem

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Follow up: Recursive solution is trivial, could you do it iteratively?

## Analysis

### Recursion

Time: $O(N)$ since the recursive function is $T(N) = 2T(N/2) + 1$
Space: $O(\log{N})$ (when balanced); $O(N)$ (worst).

### Iteration

Note:

• Null check before entering the loop.
• Null check before pushing into the stack, although Stack does allow null elements. ArrayDeque does not allow null elements.
• Push right child first!

Time: $O(N)$
Space: $O(\log{N})$ (when balanced); $O(N)$ (worst).

### Morris Traversal

Morris Traversal (reference)

Basic Idea: Morris Traversal uses the idea of threaded binary tree. It uses the left and right pointers of leaves to access the predecessor and successor in a specific traversal.

Step: (p is the current node)

Only one tiny step different from the algorithm in inorder traversal!

1. If p‘s left child is null, output p and set its right child as the new p.
2. Otherwise, then we find the predecessor of p in the left subtree.
• If the predecessor‘s right child is null, output p node, set its right child to p, and update p with its left child.
• If the predecessor‘s right child is p, set its right child to null (restore), and output p and update p with its right child.
3. Repeat the steps above until p is null.

Time: $O(N)$

Intuitively, we may think the time complexity is $O(N\log{N})$ since finding a predecessor of a node takes $O(\log{N})$. In fact, finding all predecessors of all nodes just costs $O(N)$ time because in the whole process each edge/link is only traversed twice, the first time is to locate a node and the second time is to find the predecessor.

Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.