Programming Data Structure Traversing Binary Search Tree (BST) | Recursive Binary Tree

Traversing Binary Search Tree (BST) | Recursive Binary Tree

-

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.

recursive binary search tree - cs school
Figure: Recursive Binary Search Tree

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.

traversing binary search tree - cs school
Figure: In Order traversing Binary Search Tree

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.

pre order traversing binary search tree - cs school
Figure: Pre Order Traversing 

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.

Helpful reference links: BST, Tree Traversal.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Latest Articles

Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you