Iterative preorder traversal

In last post Iterative inorder traversal , we learned how to do inorder traversal of binary tree without recursion or in iterative way. Today we will learn how to do iterative preorder traversal of binary tree. In preorder traversal, root node is processed before left and right subtrees. For example, preorder traversal of below tree would be [10,5,1,6,14,12,15],

iterative preorder traversal without recursion

We already know how to implement preorder traversal in recursive way, let’s understand how to implement it in non-recursive way.

Thought process for preorder traversal

If we look at recursive implementation, preorder traversal is: process the root, left subtree, and then right subtree.

Once the left subtree is processed, control goes to the first node in the right subtree. To emulate this behavior in a non-recursive way, it is best to use a stack. What and when push and pop will happen on the stack?
Start with pushing the root node to stack. Traversal continues till there is at least one node onto the stack.

Pop the root node from stack,process it and push it’s right and left child on to stack. Why right child before left child? Because we want to process left subtree before right subtree. As at every node, we push it’s children onto stack, entire left subtree of node will be processed before right child is popped from the stack. Algorithm is very simple and is as follows.

    1. Start with root node and push on to stack s
    2. While there stack is not empty
      1. Pop from stack current  = s.pop() and process the node.
      2. Push current.right onto to stack.
      3. Push current.left onto to stack.

Let’s take and example and see how it works. Given below tree, do preorder traversal on it without recursion.

iterative preorder traversal without recursion

Let’s start from root node(10) and push it onto stack. current = node(10).

Here loop starts, which checks if there is node onto stack. If yes, it pops that out. s.pop will return node(10), we will print it and push it’s right and left child onto stack. Preorder traversal till now : [10].

Since stack is not empty, pop from it.current= node(5). Print it and push it’s right and left child i.e node(6) and node(1) on stack.

Again, stack is not empty, pop from stack. current  = node(1). Print node. There is no right and left child for this node, so we will not push anything on the stack.

Stack is not empty yet, pop again. current= node(6). Print node. Similar to node(1), it also does not have right or left subtree, so nothing gets pushed onto stack.

iterative preorder traversal

However, stack is not empty yet. Pop. Current = node(14). Print node, and as there are left and right children, push them onto the stack as a right child before left child.

iterative preorder traversal

Stack is not empty, so pop from stack, current = node(12). Print it, as there are no children of node(12), push nothing to stack.

preorder traversal iterative

Pop again from the stack as it not empty. current = node(15). Print it. No children, so no need to push anything.

At this point, the stack becomes empty and we have traversed all node of the tree also.

Implementation

 public void preorder(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        
        if(root == null) return ;

        TreeNode currentNode = null;
        /* Step 1 : Start with root */
        stack.push(root);

        while(!stack.isEmpty()){
            /* Step 5 : Pop the node */
            currentNode = stack.pop();
            
            /* Step 2 : Print the node */
            System.out.println(currentNode.getValue());
            
            /* Step 3: Push right child first */
            if(currentNode.getRight() != null){
                stack.push(currentNode.getRight());
            }
            /* Step 4: Push left child */
            if(currentNode.getLeft() != null){
                stack.push(currentNode.getLeft());
            }
        }
    }

The complexity of iterative implementation of preorder traversal of a binary tree is O(n) as we will be visiting each node at least once. Also, there is added space complexity of stack which is O(n).

Please share if there is something wrong or missing. If you are willing to contribute and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]

Binary search tree traversals

Binary search tree traversals

Most of the problems on binary search tree can be solved using one or other traversal of tree. There are three types of binary search tree traversals : Preorder traversal, Inorder traversal and Postorder traversal. Let’s discuss each one in detail.

Preorder traversal of BST

Preorder traversal means traverse the root node first, then left subtree and at last traverse right subtree. For example, given below tree, preorder traversal will be 10,5,1,,6,19,17,21.

binary search tree traversals

As we already know that binary search tree is recursive data structure, any traversal can be solved recursively. Start with the root, then do a preorder traversal of left subtree and then at last do the preorder traversal of right subtree.

In above example,  after traversing root node(10), left subtree is traversed in preorder [5,1,6]. Same is true after traversing node(5).

Preorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        System.out.println(root.value);
        if(root.right != null) inorder(root.right);
    }
}

Inorder traversal of BST

Inorder traversal means traverse left subtree first, then root node and at last traverse right subtree. For example, given below tree, inorder traversal will be 1,5,6,10,17,19,21.

preorder travesal binary search tree

Again following the recursive strategy, if node has left child, do inorder traversal on left subtree, once inorder traversal of left subtree is done, visit root node and then again do inorder traversal of right subtree.

In above example,  before traversing root node(10), left subtree is traversed in inorder [1,5,6]. Same is true before traversing node(5).

Inorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        System.out.println(root.value);
        if(root.right != null) inorder(root.right);
    }
}

Postorder traversal of BST

Postorder traversal means traverse left subtree first, then right subtree and at last visit root node. For example, given below tree, postorder traversal will be 1,6,5,17,21,19,10.

postorder traversal of binary search tree

Again following the recursive strategy, if node has left child, do postorder traversal on left subtree, then do postorder traversal of right subtree and finally visit root node.

In above example,  before traversing root node(10), left subtree is traversed in postorder [1,6,5] and then right subtree is traversed in postorder [17,21,19] and then finally node(10).

Postorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    private void preOrder(Node root){
        if(root == null) return;

        System.out.println(root.value);
        preOrder(root.left);
        preOrder(root.right);
    }
}

In next few posts, we will discuss problems which can be solved using these traversals.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]