Reference: LeetCode
Difficulty: Medium

Problem

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

Example: 

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

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

Analysis

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  preorder(root, result);
  return result;
}

private void preorder(TreeNode x, List<Integer> result) {
  if (x == null) {
    return;
  }
  result.add(x.val);
  preorder(x.left, result);
  preorder(x.right, result);
}

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!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Preorder - Iteration
public List<Integer> preorderTraversal(TreeNode root) {
  if (root == null) {
    return new ArrayList<>();
  }
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  while (stack.size() > 0) {
    TreeNode p = stack.pop();
    result.add(p.val); // there is no null check so we must ensure that p is not null.
    if (p.right != null) stack.push(p.right);
    if (p.left != null) stack.push(p.left);
  }
  return result;
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  TreeNode p = root, pred = null;
  while (p != null) {
    if (p.left == null) { // step 1
      result.add(p.val);
      p = p.right;
    } else { // step 2
      // find predecessor
      pred = p.left;
      while (pred.right != null && pred.right != p) {
        pred = pred.right;
      }
      // check predecessor
      if (pred.right == null) { // right child is null
        result.add(p.val); // the only difference from inorder traversal
        pred.right = p;
        p = p.left;
      } else { // right child is p
        // result.add(p.val);
        pred.right = null;
        p = p.right;
      }
    }
  }
  return result;
}

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)$