### 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.

- 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 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
```

Great post actually very helpful for me, at last after 2,3 hours i found it in your blog thanks for sharing this.

ReplyDeleteCONFUSING CODE

ReplyDelete??

Deletei thought it was pretty self-explanatory..

You have mistaken BTrees with B-Trees. They are 2 very different things.

ReplyDeleteGreat! Thanks!

ReplyDeletenothing confusing straightforward code

ReplyDeleteThank you.

Can you also add:

Height of the tree.

int Tree:Height(Node * n)

{

if( n!= NULL) return 0;

else

{

return 1 + max(heigh(p->left()),heigh(p->right()))

}

And how to find a node

Thanks a lot code works fine .....thanks so much.....:)

ReplyDeleteGreat article!

ReplyDeletein the in order traversal code, what exactly does if(root) return and why/how?

ReplyDeleteI meant if( n )

ReplyDeleteSorry!

Its alway difficult for me to understand the binary search tree. can any body help me?

ReplyDeleteExcuse me sir but . .. how do I run this? I need to run it in turbo c++ 3.0 DOS . . . but it has 14 errors. . . help me please . . .

ReplyDeletethanks buddy

ReplyDeleteWill probably foreign currency trading modification ensure it is more challenging to discover the see maintained, each of those nearby or by way of the check out corporation ourselves? Smaller designs typically are not guaranteed to be able to be present and even presuming something comes incorrect, it is not necessarily clear regardless of whether portions could be offered http://www.hotwatchsale.co.uk. In addition, possibly even massive labels will most likely not likely service plan more mature wristwatches. They could, but it is not necessarily warranted. Practically everything is fastened or perhaps serviced, nevertheless much less prevalent plus aged a wrist watch might be, better complex it will be to seek out anyone who is able to operate on the application, as well as the high-priced it is able to get hold of.

ReplyDelete