Iterative Preorder Traversal of Binary tree

Introduction

In computer science, the traversal of a tree, also known as (walking to the tree), is a form of graph traversal that refers to the processing or visiting each node in a tree data structure exactly once.  (see Data Structures)

Source:- Giphy

Unlike linked lists, one-dimensional arrays or other linear data structures are traversed in a linear order. In contrast, trees can be traversed in various ways, including depth-first-order (pre-order, in-order, and post-order) or breadth-first-order (level-wise traversal). Below is an example of the DFS(depth-first-search- pre-order) and BFS(breadth-first-search):

Source:- Medium

DFS, which stands for Depth-first search, is a depth-based technique in which the search tree starts traversing at the node and explores as far as feasible in terms of the depth of the tree, as shown in the above diagram. Thus, If we try to print the values, the output will be:
 

DFS : 10 4 1 9 17 12 18

BFS : 10 4 17 1 9 12 18

This article will look at how a binary tree can be Iteratively traversed using Preorder traversal, which resides under the DFS Algorithm. In a depth-first traversal, you have three options: for example, root, left subtree, and right subtree. Preorder traversal is our emphasis; thus, we'll utilise examples of it. There are, however, several tree traversal algorithms based on the order in which you travel through these three i.e the order in which we visit the root, left subtree, and right subtree of the tree.

Now that you have seen the glimpse of the BFS vs DFS, let’s get started with today’s topic, the Iterative Preorder Traversal of Binary Trees.

What is a Preorder Traversal?

As the name suggests, the root is visited first in preorder traversal, followed by the left and right subtree. Preorder traversal can also be used to obtain a prefix expression from an expression tree.

Consider the below example to understand the Preorder Traversal:

Source: Medium

Output = F B A D C E G I H 
 

Explanation:- Suppose you are walking on a beach; the root node F is the first to be visited, followed by B, and then A. Now that there are no more left nodes to visit, you travel in the right direction, i.e., to the B node that has already been visited. Then you'll go to the right node D, then to its left node C, and finally, its right node E. The same procedure goes for the right subtree of the root node F. 

Great, now that we have learned what the preorder traversal is, let's traverse a binary tree using preorder and implement it in any programming language. 

As we are performing the Iterative approach thus, we need an additional data structure to process each node in a binary tree. Hence, we’ll use the stack data structure, which follows the LIFO( Last-in-first-out) algorithm. 

The algorithm will look like this:

Algorithm

Step 1: Make an empty stack nodeStack and add the root node to it.

Step 2: Perform the following actions until the Stack becomes empty.

a) Pop and print an item from the stack.

b) Push the right child of a popped item to stack.

c) Push the left child of a popped item to stack.

To ensure that the left subtree is handled first, the right child is pushed before the left child as a stack is a LIFO data structure.
 

The above algorithm will look like this:

Source:- Medium

In the preceding example, root node 1 is visited first. Therefore it is placed into the stack and popped out simultaneously, as stated in the prior algorithm. Because the root had no left child, the value was extracted from right subtree node 2 and popped out simultaneously. Afterwards, the right node 4 of the right subtree is pushed before the left node 3 to ensure that the left subtree is handled first. 

Thus, the result will be: 1 2 3 4 

Pseudo Code

iterativePreorder(root) 

if (root == null)

  return

s —> empty stack

s.push(root)

while (not s.isEmpty())

  root —> s.pop()

  print(root)

  if (root.right != null)

    s.push(root.right)

  if (root.left != null)

    s.push(root.left)

Now, let’s see the implementation of the stated approach:

Implementation in C++

// C++ program for Iterative preorder traversal
#include<bits/stdc++.h>
using namespace std;

// binary tree node has data, left child and the right child
struct Node
{
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
}; 

// Iterative function to perform preorder traversal
void preorderIt(Node* root)
{
    // return if the tree is empty
    if (root == nullptr)
    return;
    // create an empty stack and push the root node
    stack<Node*> s;
    s.push(root);
    // loop till the stack becomes empty
    while (!s.empty())
    {
        // pop the node from the stack and print it
        Node* curr = s.top();
        s.pop();
        // printing the current node
        cout << curr->data << " ";
        // push the right child of the popped node onto the stack before the left child 
        // the right child must be pushed first so that the left child
        // is processed first (LIFO order)
        if (curr->right) {
            s.push(curr->right);
        }
        // push the left child of the popped node into the stack
        if (curr->left) {
            s.push(curr->left);
        }
    }
}

int main()
{
    /* Construct the below tree
               1
                 \
                  \
                   2
                 /   \
                /     \
               3       4
    */
    Node* root = new Node(1);
    root->right = new Node(2);
    root->right->left = new Node(3);
    root->right->right = new Node(4);
    preorderIt(root);
    return 0;
}

Output

1 2 3 4

Time Complexity: O(n), where n is the total number of nodes in a tree as we are traversing the whole binary tree.

Space Complexity: O(h), where h is the height of the tree due to the space consumed in maintaining the stack. The height of the tree can be n for skewed binary trees, where n is the number of nodes in the binary tree.

As we can see, to perform the Iterative traversal, all nodes must be pushed onto the stack, which is not the most efficient method.