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. 😉😃💗