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


Comment