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


Comment