Given the root of a binary tree, return the Preorder traversal of its nodes’ values.
1. Introduction
In this article, I will discuss how to traverse a Binary Tree using Preorder traversal using Recursive and Iterative (without recursion) methods.
This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.
2. Content
Below are 3 examples of Binary Tree and their respective Preorder traversal results.
Example 1
Preorder Traversal = [1,2,4,5,3,6,7]
Example 2
Preorder Traversal = [1,2,4,10,3,5,7,6,8]
Example 3
Preorder Traversal = [10,5,2,7,15,12,17]
3. Preorder Traversal
Steps for Preorder traversal:
- Visit the node
- Recursively traverse the current node’s left subtree
- Recursively traverse the current node’s right subtree
The good part about recursion is that we don’t need to track the nodes in the stack. The system stack takes care of that for us. This makes our job really easy if we are implementing the traversal using recursion.
4. Preorder Traversal using Recursion
In order to save the result of traversal, we need to use ArrayList.
Below is the code for Preorder Traversal of the Binary Tree using Recursion.
public List<Integer> preorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return Collections.unmodifiableList(result);
}
private void preorder(TreeNode root, List<Integer> result) {
if(root != null) {
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
Time Complexity:
- O(n) where n is the total number of nodes in the Binary Tree.
Space Complexity:
- O(h) where h is the height of the tree. If the tree is skewed, then the factor h degrades to n, where n is the total number of nodes in the tree. Below is what a skewed tree looks like.
5. Preorder Traversal using Iteration
In Order to write code using an iterative way, we need to use a Stack data structure to save the elements that we are traversing. In Recursion, we use system stack, but in Iteration we need to use external Stack to traverse Binary Tree using Preorder traversal.
Below is the code to traverse a Binary Tree using Preorder Traversal.
public List<Integer> preorderTraversal(TreeNode root) {
TreeNode curr = root;
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
// Visit the node
list.add(curr.val);
stack.push(curr);
// Push the left subtree in the stack.
curr = curr.left;
}
curr = stack.pop();
// Visit the right subtree
curr = curr.right;
}
return Collections.unmodifiableList(list);
}
Time Complexity:
- O(n) where n is the total number of nodes in the Binary Tree.
Space Complexity:
- O(h) where h is the height of the tree. If the tree is skewed, then the factor h degrades to n, where n is the total number of nodes in the tree.
6. Conclusion
In this article, we saw Preorder Traversal of the Binary Tree using Recursion and Iteration.