By Frank Luo
The Tree Traversal Algorithms are used to traversal the tree including Binary Tree and N-ary Tree.
- Binary Tree Traversal
94. Binary Tree Inorder Traversal
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal
- N-ary Tree Traversal
589. N-ary Tree Preorder Traversal
590. N-ary Tree Postorder Traversal
Binary Tree
PreOrder
Algorithm Preorder(tree)
- Visit the root;
- Traverse the left subtree, i.e., call Preorder(left-subtree);
- 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)
- Space Complexity: 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)
- Space Complexity: O(n)
InOrder
Algorithm Inorder(tree)
- Traverse the left subtree, i.e., call Inorder(left-subtree);
- Visit the root;
- 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)
- Space Complexity: 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)
- Space Complexity: O(n)
PostOrder
Algorithm Postorder(tree)
- Traverse the left subtree, i.e., call Postorder(left-subtree);
- Traverse the right subtree, i.e., call Postorder(right-subtree);
- 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)
- Space Complexity: 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)
- Space Complexity: 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)
- Space Complexity: 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)
- Space Complexity: 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)
- Space Complexity: 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)
- Space Complexity: 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. 😉😃💗