Preorder, Inorder and Postorder tree traversals

PreOrder traversal

  • In Pre-Order tree traversal, the root data is accessed as soon as the root is visited. After the root data is accessed, the left child of the root node is visited and then the right child.
  • The traversal is recursive in nature, i.e the left child and the right child are traversed similarly to the parent node.
  • Thus the preorder traversal recursively follows the sequence Print node’s data -> Visit Left_Child_Of_Node -> Visit Right_Child_Of_Node.

Algorithm PreOrder Traversal

Recursive Iterative
PreOrder ( Node node )
     If ( node != null ) then
         Print node’s data
         PreOrder ( node’s left child )
         PreOrder ( node’s right child )
PreOrder ( Node node )
     Stack stk
     While ( node != NULL or stk is not empty ) do
          If ( node != NULL ) then
              Print node’s data
              Push node on stack stk.
              node = node’s left child.
          If ( node == NULL ) then
              node = node at stk top.
              Pop stk.
              node = node’s right child.

Example of pre-order traversal : 9, 5, 3, 7

PreOrder_Traversal



InOrder Traversal

  • In In-Order tree traversal, the left child of a node is visited first, followed by the data of the node and then the right child of the node.
  • The traversal is recursive in nature. i.e the left child and the right child are traversed similarly to the parent node.
  • Thus the preorder traversal recursively follows the sequence Visit Left_Child_Of_Node -> Print node’s data -> Visit Right_Child_Of_Node.

Algorithm InOrder Traversal

Recursive Iterative
InOrder ( Node * node )
     If ( node != null ) then
         InOrder ( node’s left child )
         Print node’s data
         InOrder ( node’s right child )
InOrder ( Node node )
     Stack stk
     While ( node != NULL or stk is not empty ) do
          If ( node != NULL ) then
              Push node on stk top.
              node = node’s left child.
          If ( node == NULL ) then
              node = node at stk top.
              Pop stk.
              Print node’s data
              node = node’s right child.

Example of an in-order traversal : 3, 5, 7, 9

InOrder_Traversal



PostOrder Traversal

  • In Post-Order tree traversal, the left child of a node is visited first, then the right child of the node followed by the data of the node.
  • Post order traversal is recursive in nature. i.e the left child and the right child are traversed similarly to the parent node.
  • Thus the preorder traversal recursively follows the sequence Visit Left_Child_Of_Node -> Visit Right_Child_Of_Node -> Print node’s data.

Algorithm PostOrder Traversal

The iterative algorithm for PostOrder traversal makes use of 2 stacks.

  • Stack stk is used for processing the nodes.
  • Stack stk_postorder is used for storing the postorder of the nodes.
Recursive Iterative
PostOrder ( Node * node )
     If ( node != null ) then
         PostOrder ( node’s left child )
         PostOrder ( node’s right child )
         Print node’s data
PostOrder ( Node node )
     Stack stk
     Stack stk_postorder

     If ( node != NULL ) then
          Push node on stk top.

     While ( stk is not empty ) do
          node = node at stk top.
          Pop stk top.
          Push node on stk_postorder.
          If ( node’s left child != null ) then
              Push node’s left child on stk.
          If ( node’s right child != null ) then
              Push node’s right child on stk.

     While ( stk_postorder is not empty ) do
          Print data of node at the top of stk_postoder.
          Pop stk_postoder.

Example of an post-order traversal : 3, 7, 5, 9

PostOrder_Traversal



Data structure used for pre-order, in-order and post-order traversals : Stack
Time complexity of pre-order, in-order and post-order traversals : O ( n ), where n is the number of nodes in the graph.


Pre-Order, In-Order and Post-Order traversal implementation

from collections import deque

class Node :
    def __init__(self, val, left_node, right_node) :
        self.val = val
        self.left = left_node
        self.right = right_node

def PreOrderRec(node) :
    if node :
        print(node.val, end = ' ')
        PreOrderRec(node.left)
        PreOrderRec(node.right)

def PreOrder(node) :
    stack = deque()
    while (node or stack) :
        if node :
            print(node.val, end = ' ')
            stack.appendleft(node)
            node = node.left
        if node == None:
            node = stack.popleft() # Node at the top of stack
            node = node.right

def InOrderRec(node) :
    if node :
        InOrderRec(node.left)
        print(node.val, end = ' ')
        InOrderRec(node.right)

def InOrder(node) :
    stack = deque()
    while (node or stack) :
        if node :
           stack.appendleft(node)
           node = node.left
        if node == None :
            node = stack.popleft() # Node at the top of stack
            print(node.val, end =' ')


def PostOrderRec(node) :
    if node :
        PostOrderRec(node.left)
        PostOrderRec(node.right)
        print(node.val, end = ' ')

def PostOrder(node) :
    stack_postorder = deque()
    stack = deque()

    if node :
       stack.append(node)

    while (stack) :
        # stack_postorder stores the order of the elements to be traversed in
        # postorder
        stack_postorder.appendleft(stack.popleft())

        if stack_postorder[0].left :
           stack.appendleft(stack_postorder[0].left)

        if stack_postorder[0].right :
           stack.appendleft(stack_postorder[0].right)

    while (stack_postorder) :

        print(stack_postorder.popleft().val, ' ')

def main() :

    node_3 = Node(3, None, None); # Leaf Node
    node_7 = Node(7, None, None); # Leaf Node
    node_12 = Node(12, None, None); # Leaf Node
    node_18 = Node(18, None, None); # Leaf Node
    node_16 = Node(16, node_12, node_18)
    node_5 = Node(5, node_3, node_7)
    root = Node(9, node_5, node_16)

    print("---- Recursive method ----")
    print("Pre-Order  :", end = ' ')
    PreOrderRec(root)
    print("\nIn-Order   :", end = ' ')
    InOrderRec(root)
    print("\nPost-Order :", end = ' ')
    PostOrderRec(root)

    print("\n\n---- Stack based method ----")
    print("Pre-Order  :", end = ' ')
    PreOrderRec(root)
    print("\nIn-Order   :", end = ' ')
    InOrderRec(root)
    print("\nPost-Order :", end = ' ')
    PostOrderRec(root)

if __name__ == "__main__" :
    main()

Output

---- Recursive method ----
Pre-Order  : 9 5 3 7 16 12 18 
In-Order   : 3 5 7 9 12 16 18 
Post-Order : 3 7 5 12 18 16 9 

---- Stack based method ----
Pre-Order  : 9 5 3 7 16 12 18 
In-Order   : 3 5 7 9 12 16 18 
Post-Order : 3 7 5 12 18 16 9
#include <iostream>
#include <stack>
using namespace std;

class Node{

    public:
    int data;
    Node * left;
    Node * right;
    Node(int n, Node* left_, Node* right_):data(n),left(left_),right(right_){}
    Node(int n):data(n),left(nullptr),right(nullptr){}
};

void PreOrder_Recursive(Node * node){

    if (node != nullptr) {
        cout << node->data << " ";      // Access the data 
        PreOrder_Recursive(node->left);  // Visit current node's left node
        PreOrder_Recursive(node->right); // Visit current node's right node
    }
}

void PreOrder (Node * node) {

    stack<Node*> stk;

    while (node != nullptr || !stk.empty()) {
        if (node != nullptr) {
            cout << node->data << " ";
            stk.push(node);
            node = node->left;
        }
        if (node == nullptr) {
            node = stk.top();
            stk.pop();
            node = node->right;
        }
    }
}

void InOrder_Recursive (Node * node) {

    if (node != nullptr) {
        InOrder_Recursive(node->left);
        cout << node->data << " ";
        InOrder_Recursive(node->right);
    }
}

void InOrder (Node * node) {

    stack<Node *> stk;

    while (node != nullptr || !stk.empty()) {
        if (node != nullptr) {
            stk.push(node);
            node = node->left;
        }
        if (node == nullptr) {
            node = stk.top();
            stk.pop();
            cout << node->data << " ";
            node = node->right;
        }
    }
}

void PostOrder_Recursive (Node * node) {

    if (node != nullptr) {
        PostOrder_Recursive(node->left);
        PostOrder_Recursive(node->right);
        cout << node->data << " ";
    }
}

void PostOrder (Node * node) {

    stack<Node *> stk_postorder;
    stack<Node *> stk;

    if (node != nullptr) {
        stk.push(node);
    }

    while (!stk.empty()) {

        node = stk.top();
        stk_postorder.push(node);
        stk.pop();

        if (node->left != nullptr) {
            stk.push(node->left);
        }

        if (node->right != nullptr) {
            stk.push(node->right);
        }
    }

    while (!stk_postorder.empty()) {
        cout << stk_postorder.top()->data << " ";
        stk_postorder.pop();
    }
}

/* Constructed binary tree is
               9
             /   \
            5     16
          /  \   /  \
         3   7  12   18
*/

int main() {

    Node node_3 (3, nullptr, nullptr);
    Node node_7 (7, nullptr, nullptr);
    Node node_12 (12, nullptr, nullptr);
    Node node_18 (18, nullptr, nullptr);
    Node node_5 (5, &node_3, &node_7);
    Node node_16 (16, &node_12, &node_18);
    Node root (9, &node_5, &node_16);

    cout << "---- _Recursive method ----" << endl;
    cout << "Pre-Order  : "; PreOrder_Recursive(&root); cout << endl;
    cout << "In-Order   : "; InOrder_Recursive(&root); cout << endl;
    cout << "Post-Order : "; PostOrder_Recursive(&root); cout << endl;

    cout << "---- Stack based ----" << endl;
    cout << "Pre-Order  : "; PreOrder(&root); cout << endl;
    cout << "In-Order   : "; InOrder(&root); cout << endl;
    cout << "Post-Order : "; PostOrder(&root); cout << endl;

    return 0;
}

Output

---- Recursive method ----
Pre-Order  :  9 5 3 7 16 12 18 
In-Order   :  3 5 7 9 12 16 18 
Post-Order :  3 7 5 12 18 16 9 

---- Stack based ----
Pre-Order  :  9 5 3 7 16 12 18 
In-Order   :  3 5 7 9 12 16 18 
Post-Order :  3 7 5 12 18 16 9 
import java.util.Stack;

class TreeTraversals {

    static class Node {
        int data;
        Node left;
        Node right;
        Node () {}
        Node (int data) { this.data = data; }
        Node (int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    void PreOrderRecursive (Node node) {

        if (node != null) {
            System.out.print(node.data + " "); // Access the data 
            PreOrderRecursive(node.left);      // Visit current node's left node
            PreOrderRecursive(node.right);     // Visit current node's right node
        }
    }

    void PreOrder (Node node) {

        Stack<Node> stk = new Stack<>();

        while (node != null || !stk.empty()) {
            if (node != null) {
                System.out.print (node.data + " ");
                stk.push(node);
                node = node.left;
            }
            if (node == null) {
                node = stk.peek();
                stk.pop();
                node = node.right;
            }
        }
    }

    void InOrderRecursive (Node node) {

        if (node != null) {
            InOrderRecursive (node.left);       // Visit current node's left node
            System.out.print (node.data + " "); // Access the data
            InOrderRecursive (node.right);      // Visit current node's right node 
        }
    }

    void InOrder (Node node) {

        Stack<Node> stk = new Stack<>();

        while (node != null || !stk.empty()) {
            if (node != null) {
                stk.push(node);
                node = node.left;
            }
            if (node == null) {
                node = stk.peek();
                stk.pop();
                System.out.print (node.data + " ");
                node = node.right;
            }
        }
    }

    void PostOrderRecursive (Node node) {
        if (node != null) {
            PostOrderRecursive (node.left);     // Visit current node's left node
            PostOrderRecursive (node.right);    // Visit current node's right node
            System.out.print (node.data + " "); // Access the data
        }
    }

    void PostOrder (Node node) {

        Stack<Node> stk_postorder = new Stack<>();
        Stack<Node> stk = new Stack<>();

        if (node != null) {
            stk.push(node);
        }

        while (!stk.empty()) {

            stk_postorder.push(stk.peek());
            stk.pop();

            if (stk_postorder.peek().left != null) {
                stk.push(stk_postorder.peek().left);
            }

            if (stk_postorder.peek().right != null) {
                stk.push(stk_postorder.peek().right);
            }
        }

        while (!stk_postorder.empty()) {
            System.out.print(stk_postorder.peek().data + " ");
            stk_postorder.pop();
        }
    }

    /* Constructed binary tree is
                   9
                 /   \
                5     16
              /  \   /  \
             3   7  12   18
    */

    public static void main (String[] args) {

        Node n3  = new Node(3);
        Node n7 = new Node(7);
        Node n12 = new Node(12);
        Node n18 = new Node(18);
        Node n5 = new Node(5, n3, n7);
        Node n16 = new Node(16, n12, n18);
        Node root = new Node(9, n5, n16);

        TreeTraversals t = new TreeTraversals();

        System.out.println ("---- Recursive method ----\n");
        System.out.print("Pre-Order   : "); t.PreOrderRecursive (root);  System.out.print("\n");
        System.out.print("In-Order    : "); t.InOrderRecursive (root);   System.out.print("\n");
        System.out.print("Post-Order  : "); t.PostOrderRecursive (root); System.out.print("\n");

        System.out.println ("\n---- Stack based method ----\n");
        System.out.print("Pre-Order  : "); t.PreOrder (root);  System.out.print("\n");
        System.out.print("In-Order   : "); t.InOrder (root);   System.out.print("\n");
        System.out.print("Post-Order : "); t.PostOrder (root); System.out.print("\n");
    }
}

Output

---- Recursive method ----

Pre-Order   : 9 5 3 7 16 12 18 
In-Order    : 3 5 7 9 12 16 18 
Post-Order  : 3 7 5 12 18 16 9 

---- Stack based method ----

Pre-Order   : 9 5 3 7 16 12 18 
In-Order    : 3 5 7 9 12 16 18 
Post-Order  : 3 7 5 12 18 16 9 


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.