StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Monday, June 17, 2013

C++ Pre-Order, In-Order, Post-Order Traversal of Binary Search Trees

 June 17, 2013     Data Structures     No comments   

This article explains the depth first search (DFS) traversal methods for binary search search trees.

Pre-Order, In-Order, Post-Order traversal of Binary Search Trees (BST)

  • Pre-Order, In-Order and Post-Order are depth first search traversal methods for binary search trees.
  • Starting at the root of binary tree the order in which the nodes are visited define these traversal types.
  • Basically there are 3 main steps. (1) Visit the current node, (2) Traverse the left node and (3) Traverse the right nodes.
From Wikipedia,
  • To traverse a non-empty binary search tree in pre-order, perform the following operations recursively at each node, starting with the root node: 1. Visit the root. 2. Traverse the left sub-tree. 3. Traverse the right sub-tree.
  • To traverse a non-empty binary search tree in in-order (symmetric), perform the following operations recursively at each node: 1. Traverse the left sub-tree. 2. Visit the root. 3. Traverse the right sub-tree.
  • To traverse a non-empty binary search tree in post-order, perform the following operations recursively at each node: 1. Traverse the left sub-tree. 2. Traverse the right sub-tree. 3. Visit the root.

Implementation for binary search tree (BST) traversal

#include <iostream>
using namespace std;

// Node class
class Node {
    int key;
    Node* left;
    Node* right;
public:
    Node() { key=-1; left=NULL; right=NULL; };
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
};

// Tree class
class Tree {
     Node* root;
public:
     Tree();
     ~Tree();
     Node* Root() { return root; };
     void addNode(int key);
     void inOrder(Node* n);
     void preOrder(Node* n);
     void postOrder(Node* n);
private:
     void addNode(int key, Node* leaf);
     void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
     root = NULL;
}

// Destructor
Tree::~Tree() {
     freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
       freeNode(leaf->Left());
       freeNode(leaf->Right());
       delete leaf;
    }
}

// Add a node
void Tree::addNode(int key) {
     // No elements. Add the root
     if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
        root = n;
     }
     else {
       cout << "add other node ... " << key << endl;
       addNode(key, root);
     }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
          addNode(key, leaf->Left());
       else {
          Node* n = new Node();
          n->setKey(key);
          leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
          addNode(key, leaf->Right());
       else {
          Node* n = new Node();
          n->setKey(key);
          leaf->setRight(n);
       }
    }
}

// Print the tree in-order
// Traverse the left sub-tree, root, right sub-tree
void Tree::inOrder(Node* n) {
    if ( n ) {
       inOrder(n->Left());
       cout << n->Key() << " ";
       inOrder(n->Right());
    }
}

// Print the tree pre-order
// Traverse the root, left sub-tree, right sub-tree
void Tree::preOrder(Node* n) {
    if ( n ) {
       cout << n->Key() << " ";
       preOrder(n->Left());
       preOrder(n->Right());
    }
}

// Print the tree post-order
// Traverse left sub-tree, right sub-tree, root
void Tree::postOrder(Node* n) {
    if ( n ) {
       postOrder(n->Left());
       postOrder(n->Right());
       cout << n->Key() << " ";
    }
}


// Test main program
int main() {
   Tree* tree = new Tree();
   tree->addNode(30);
   tree->addNode(10);
   tree->addNode(20);
   tree->addNode(40);
   tree->addNode(50);

   cout << "In order traversal" << endl;
   tree->inOrder(tree->Root());
   cout << endl;

   cout << "Pre order traversal" << endl;
   tree->preOrder(tree->Root());
   cout << endl;

   cout << "Post order traversal" << endl;
   tree->postOrder(tree->Root());
   cout << endl;

   delete tree;
   return 0;
}
OUTPUT:-
add root node ... 30
add other node ... 10
add other node ... 20
add other node ... 40
add other node ... 50
In order traversal
10 20 30 40 50
Pre order traversal
30 10 20 40 50
Post order traversal
20 10 50 40 30
Email ThisBlogThis!Share to XShare to Facebook

Related Posts:

  • C++ Pre-Order, In-Order, Post-Order Traversal of Binary Search Trees This article explains the depth first search (DFS) traversal methods for binary search search trees. Pre-Order, In-Order, Post-Order traversal of Bi… Read More
  • C++ Singly Linked ListsThis article explains the concept of singly linked list data structure and provides a sample implementation. Singly Linked List Introduction Lin… Read More
  • C++ QueuesThis article explains the queue data structure and demonstrates sample implementation using C++. Queue Introduction Queue is a first-in, … Read More
  • C++ Level Order Traversal of Binary Search TreesThis article explains level-order traversal/ Breadth First (BFS) traversal of binary search tree with a sample implementation in C++. Level order tra… Read More
  • C++ HeapsThis article gives an introduction to heap data structure and provides a sample implementation in C++. Heap introduction Heap is a binary tree t… Read More
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Python FastAPI file upload and download
    In this article, we will look at an example of how to implement a file upload and download API in a Python FastAPI microservice. Example bel...
  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Accessing the Kubernetes API
    In this article, we will explore the steps required to access the Kubernetes API and overcome common challenges. All operations and communic...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Scheduling jobs in Python
    When developing applications and microservices we run into scenarios where there is a need to run scheduled tasks. Examples include performi...
  • Using Tekton to deploy KNative services
    Tekton is a popular open-source framework for building continuous delivery pipelines. Tekton provides a declarative way to define pipelines ...

Copyright © 2025 StackStalk