The Binary Search Tree (BST), and its property we have discussed in earlier topic in data structure section. In this article we will talk about Traversing Binary Search Tree. Traversing the BST means traveling or walking along the tree. There are three different way we can traverse a Binary Search Tree. Which is our topic of discussion in this article. Before moving anong, let’s start by understanding the recursive binary search tree.
Recursive Binary Tree
Recursion is an appropriate term we generally use to define a structure that has similar and repeated pattern. A recursive structure we can observe in BST, because it consists of multiple subtrees, that has similar structure as BST itself. Generally, BST includes a root or parent node, left- right child and grandchild. Similar to a subtrees. For every subtree, there is also a parent node and its child, or grandchild.
We can define a binary search tree is recursive in following way:
A BST is either empty or consists of – 1. a node storing a single element called root. 2. a left-subtree. 3. a right-subtree.
For the recursive structure of BST, it is considered as efficient data structure. Because we can traverse each node of the tree by recursively visiting each node in the left and right subtrees. Now, let’s talk about how we can recursively traverse a binary search tree.
Traversing Binary Search Tree
The reason we need to traverse a tree most of the cases to search an element, to insert an element, or to delete an element from the tree. There are three way we can traverse a binary tree. Those are:
In Order Traversal: In this traversal we first look at the nood, then we recursively visit the left child, then we visit the root, and after that we recursively visit the right child.
According to Figure: Inorder traversal, we will go left, left until we find the bottom leaf node 11, and print the data first. Then we will go up and print its parent node 20. After that we will go right- 29, a parent, its left-child 28, we will print it. After that up and its parent 29, print it. then right child empty, so go up. 20 visited. go up root 41, print it. Then go right 65, its left child 50, print it, and so on.
So result output after inorder traversing we get: 11, 20, 26, 29, 41, 50, 65. Next we have preorder traversal.
Pre Order Traversal: In this traversal, we visit the root first, then we recursively visit the left child, and finally, recursively visit the right child.
So, in pre order traversing of above binary tree, we will visit the root 41 first, and then left child 20, which also a parent of subtree, therefore we will print 20. Then we will visit recursively its left child 11, then right 29, and so on and so forth. So, the final output from the Pre Order traversal will be: 41, 20, 11, 29, 26, 65, 50.
Post Order traversal: Similarly, in post order traversal, we recursively visit the left node first, and then recursively the right node, and finally the root. For above illustration, if we print nodes in post-order traversal, our result would be: 11, 26, 29, 20, 50, 65, 41.