﻿ C++ Pre-Order, In-Order, Post-Order Traversal of Binary Search Trees ~ Programming Tutorials by SourceTricks
Monday, June 17, 2013

## 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 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 inOrder(Node* n);
void preOrder(Node* n);
void postOrder(Node* n);
private:
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;
}
}

// 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;
}
}

void Tree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() ) {
if ( leaf->Left() != NULL )
else {
Node* n = new Node();
n->setKey(key);
leaf->setLeft(n);
}
}
else {
if ( leaf->Right() != NULL )
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();

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
In order traversal
10 20 30 40 50
Pre order traversal
30 10 20 40 50
Post order traversal
20 10 50 40 30``````

Name

Email *

Message *