Iterative Preorder Traversal
Get started
জয় শ্রী রাম
🕉Preorder Traversal:
This is simple. In Preorder Traversal we first visit the current node, then the entire left subtree before visiting right child. Since this is iterative implementation, we would definitely need a stack. So let's see step by step how to build the iterative preorder algorithm implementation:
Step#0. Initialization: Initialize the stack by pushing root node in it. That way root now is in line to be processed.
Step#1. Visit the current node. The current node will be at the top of the stack. So just pop the stack.
Step#2. We need to process the entire left subtree next, before processing right child node (and right sub tree). This means, push left child of the current node in the stack.
Step#3. Now push right child of the current node in the stack so that this node is in the stack and will be visited once the left subtree of the current node is done processing.
Let's look at the code now:
Java code:
public List<Integer> preorder(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<Node> stack = new ArrayDeque<>();
stack.add(root);
while (!stack.isEmpty()) {
// visit
Node currNode = stack.removeLast();
// process
res.add(currNode.val);
if (currNode.right != null) {
stack.add(currNode.right);
}
if (currNode.left != null) {
stack.add(currNode.left);
}
}
return res;
}
Python Code:
Login to Access Content
Must Read Chapters:
- Iterative Postorder Traversal
-
Iterative Postorder Traversal
w/ Single Stack -
Powerful Approach of
Iterative Inorder Traversal - How to track traversed paths in DFS
