Reference: LeetCode
Difficulty: Medium

Problem

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

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> inorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  inorder(root, result);
  return result;
}

private void inorder(TreeNode x, List<Integer> result) {
  if (x == null) {
    return;
  }
  inorder(x.left, result);
  result.add(x.val);
  inorder(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:

  • The condition is p != null || !stack.isEmpty().
  • Notice p = p.right:
    • If p.right is null, the next node would be the node currently in the stack.
    • Otherwise, the next node would be the leftmost node of the right child (after continuous pushing).

“while” version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  TreeNode p = root;
  while (p != null || stack.size() > 0) {
    while (p != null) { // go to the leftmost node
      stack.push(p);
      p = p.left;
    } // p -> null
    
    p = stack.pop();
    result.add(p.val); // visit
    
    p = p.right; // go to right (1. p == null -> pop() or 2. p != null -> push its left child)
  }
  return result;
}

“if” version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  TreeNode p = root;
  while (p != null || stack.size() > 0) {
    if (p != null) {
      stack.push(p);
      p = p.left;
    } else { // p is null
      p = stack.pop();
      result.add(p.val);
      p = p.right;   
    }
  }
  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)

  1. If p‘s left child is null, output p and set its right child as the new p.
  2. If p‘s left child is not null, then we find the predecessor of p in the left subtree.
    1. If the predecessor‘s right child is null, set its right child to p, and update p with its left child.
    2. 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
public List<Integer> inorderTraversal(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
        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)$