• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



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:



This is a Premium content.
Please subscribe to Algorithms course to access the code.






Must Read Chapters:



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave