Tree data structure tutorial 4. Binary Search Tree Introduction
In this tutorial we shall learn about following topics:
4.1 Binary Search Tree Introduction
4.2 Example of a Binary Search Tree.
4.3 How to search for an element in BST
4.4 How to insert an element in BST
4.1 Binary Search Tree Introduction
Binary Search Tree [BST] is a tree, where the data will be placed in a particular order. Because of this kind if organization, it will help to insert and search the data efficiently.
In a binary tree, for each node, if the value of all the nodes in left sub tree is lesser and the value of all the nodes in the right sub tree is greater, then such binary tree is called as Binary Search Tree.
Definition: A Binary Tree in which for each node, the value of all the nodes in the left sub tree is lesser or equal and value of all the nodes in right sub tree is greater, then such a binary tree is called as Binary search tree.
4.2 Example of a Binary Search Tree.
From the above image, “15”is the root node. The value of the nodes at left sub tree is lesser than the root node and right sub tree is greater than the root node.
Now, if we consider the sub tree at node “10”, left node has less value and right node has higher value.
4.3 Now let us see, how to search for an element in BST
Consider the below tree. The value to be searched is 12. Below are the steps that we follow to search for element 12.
First check the root node, in our case, the element 12 is less than the root node. Hence move towards left.
Then check the value of new node i.e 10. As 12 is greater than 10, move towards right.
Then we get our search key.
4.4 Now let us see, how to insert an element in BST
Now let us insert the element 19.
Start from the root node, “15”. As the value “19” is greater than root node “15”, we move towards right side of the tree.
Now we have reached node “20”. As “19” is lesser than “20”, we move towards left to node 18.
Now “19” is greater than “18”, we insert it to the right of node “18”.
