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

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

This article explains the depth first search (DFS) traversal methods for binary search search trees.
  • 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.

Sample implementation for binary search tree (BST) traversal

#include <iostream>using namespace std;// Node classclass 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 classclass 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);};// ConstructorTree::Tree() {root = NULL;}// DestructorTree::~Tree() {freeNode(root);}// Free the nodevoid Tree::freeNode(Node* leaf){if ( leaf != NULL ){freeNode(leaf->Left());freeNode(leaf->Right());delete leaf;}}// Add a nodevoid Tree::addNode(int key) {// No elements. Add the rootif ( 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-treevoid 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-treevoid 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, rootvoid Tree::postOrder(Node* n) {if ( n ) {postOrder(n->Left());postOrder(n->Right());cout << n->Key() << " ";}}// Test main programint 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 ... 30add other node ... 10add other node ... 20add other node ... 40add other node ... 50In order traversal10 20 30 40 50Pre order traversal30 10 20 40 50Post order traversal20 10 50 40 30