Friday, November 14, 2014

Binary Search Tree Traversal Algorithms

I hereby post my version of the inorder, preorder and postorder code in c++. Please provide your valuable feedback or additions to the code.

I am also providing a simple explanation here along with the download for an explanation of how to perform these simple tree traversals. Please provide your comments on the documentation as well.

In  a Binary Search Tree, every node has the left subtree with elements lesser than itself and the right subtree withe elements greater than (or equal) to itself. In a BST, the tree can be traversed using the following mechanisms.

Inorder Tree Traversal - C++
For a set of elements, that are inserted as mentioned below, the inorder tree traversal algorithms is as follows. It is recursive in nature and can start at root always.

1. Traverse the Left Subtree
2. Print the Node
3. Traverse the Right Subtree

Postorder Tree Traversal - C++
Postorder is a similar algorithm in nature - except that the traversal order is different.

1. Traverse the Left Subtree
2. Traverse the Right Subtree
3. Print the Node

Preorder Tree Traversal - C++
Whenever we want to traverse the node before the two subtrees, we use pre-order traversal.

1. Print the Node
2. Traverse the Left Subtree
3. Traverse the Right Subtree

We use the following insertion order for all algorithms above: 9 7 6 1 3 5 4 2 8

You can run the C++ code to see the output yourself. It is left as an exercise (or direct code reuse) for the user.

No comments: