Tree Traversals: PreOrder, InOrder and PostOrder

By Frank Luo

Leetcode Binary Tree Traversal such problems:

  1. Binary Tree Traversal
    94. Binary Tree Inorder Traversal
    144. Binary Tree Preorder Traversal
    145. Binary Tree Postorder Traversal

  2. N-ary Tree Traversal
    589. N-ary Tree Preorder Traversal
    590. N-ary Tree Postorder Traversal

Binary Tree

PreOrder

1
2
3
4
Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)

Recursive

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

public void preOrder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}

list.add(root.val);
preOrder(root.left, list);
preOrder(root.right, list);
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return ans;
}
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
ans.add(root.val);
root = root.left;
}

root = stack.pop();
root = root.right;
}

return ans;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

InOrder

1
2
3
4
Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal_rec(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inOrder(root, ans);
return ans;
}

public void inOrder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
if (root.left != null) {
inOrder(root.left, list);
}
list.add(root.val);
if (root.right != null) {
inOrder(root.right, list);
}
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return ans;
}

while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}

root = stack.pop();
ans.add(root.val);
root = root.right;
}

return ans;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

PostOrder

1
2
3
4
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.

Recursive

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

public void postOrder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}

postOrder(root.left, list);
postOrder(root.right, list);
list.add(root.val);
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Iteration

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> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return ans;
}

TreeNode prev = null;
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}

root = stack.pop();
if (root.right == null || root.right == prev) {
ans.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}

return ans;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

N-ary Tree Traversal

PreOrder

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorder(Node root) {
List<Integer> ans = new ArrayList<>();
preOrderTraversal(root, ans);
return ans;
}

public void preOrderTraversal(Node root, List<Integer> list) {
if (root == null) {
return;
}
list.add(root.val);
List<Node> children = root.children;
for (Node child : children) {
preOrderTraversal(child, list);
}
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> preorder(Node root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}

Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
Node node = stack.pop();
ans.add(node.val);
List<Node> children = node.children;
int size = children.size();
for (int i = size - 1; i >= 0; i--) {
stack.push(children.get(i));
}
}

return ans;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

PostOrder

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> postorder_rec(Node root) {
List<Integer> ans = new ArrayList<>();
postOrderTraversal(root, ans);
return ans;
}

public void postOrderTraversal(Node root, List<Integer> list) {
if (root == null) {
return;
}
List<Node> children = root.children;
for (Node child : children) {
postOrderTraversal(child, list);
}
list.add(root.val);
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> postorder(Node root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}

Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
Node node = stack.pop();
ans.add(node.val);
List<Node> children = node.children;
int size = children.size();
for (int i = 0; i < size; i++) {
stack.push(children.get(i));
}
}

Collections.reverse(ans);
return ans;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗