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:



Instructor:



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



Help Your Friends save 40% on our products

wave