Binary Search Tree :
It is tree which have one unique root node and all other nodes have at most two children’s ,with restriction that left children must be less than node and right children must be equal to or greater than node .
For Example :
10
/ \
8 12
/ \
7 9
Fig 1.0
In Figure 1.0 node with value 10 is root of tree.node with value 8 is its left child and node with value 12 is its right child.
Binary search Tree Insertion :
To insert any node in binary search tree , first we will define tree node structure .Lets assume our binary search tree will contain only integer values .We can then define tree node like this :
struct NODE
{
int data;
struct NODE *left;
struct NODE *right;
};
here "data" is value to be stored in node , while pointers left and right are pointing to left subtree and right subtree respectively.
Binary search tree insertion will consists of accounting two cases , first if tree is empty ,other one if tree already have some node .
Lets take first case , if tree is empty :
In this case,all we need to do is create new node and make this node as root of tree.
struct NODE *root;
root = new struct NODE;
root->data = 10;
root->left = root->right = NULL;
Second case , If tree already contains some node :
In this case , we will recursively find position of node to be inserted .If this node to be inserted is less than root node , we will try to find recursive suitable position in left subtree of root node , else we will try to find suitable position recursively in right subtree.
Consider fig .1.0 Above , and we want to insert node with value 5 into it .
First we will compare it with root node which have value 10 , since 5 <10 , we will search left subtree recursively.
Next we will compare it with 8 , since 5<8 , we will search in left subtree of 8 , which here found to be 7 . In our last comparision we will compare it with 7 . As 5<7 .
we will insert node with value 5 as left child of node with value 7.
Result of this insertion will be :
10
/ \
8 12
/ \
7 9
/
5
Fig 2.0
Complete function to insert a node in binary search tree :
struct NODE* insertNode(struct NODE *root,int val)
{
if(root == NULL)
{
root = new struct NODE;
root->data = val;
root->left = root->right = NULL;
return root;
}
else
{
if(val<root->data)
{
root->left = insertNode(root->left,val);
return root;
}
else
{
root->right = insertNode(root->right,val);
return root;
}
}
}
To call this insertion function,use below statements in your code :
struct NODE*root = NULL;
root = insertNode(root,10);
In order Traversal of BST:
Now that we have inserted nodes in our binary search tree , we must be having some way to view tree (i.e print nodes in any specific order) .
There are tree ways to traverse a binary search :
1)Pre Order traversal (Node , Left Child , Right child)
2)Post Order traversal (Left Child,Right child, Node)
3)In Order traversal (Left child,Node ,Right child) - Print in sorted order
Consider Fig 2.0 Again :
10
/ \
8 12
/ \
7 9
/
5
Pre Order Traversal : 10,8,7,5,9,12
Post Order Traversal : 5,7,9,8,12,10
In Order Traversal : 5,7,8,9,10,12
Traditionally In Order traversal is used to display a tree , I will do the same :
Recursively print call left subtree , print node then recursively call right subtree.
Complete function to print nodes in In Order Traversal :
void printTree(struct NODE* root)
{
if(root != NULL)
{
printTree(root->left);
std::cout<<root->data<<std::endl;
printTree(root->right);
}
}
Level Order Traversal Of BST :
As we are trying to solve problem of inserting sorted array into balanced binary search tree ,Printing nodes in In Order traversal wont make , a guarantee that we have indeed inserted nodes in balanced BST , since In Order traversal always prints nodes in sorted ascending order.
To Overcome this situation , I will be printing nodes in level order traversal .Print Node level by level , start from level 0 (i.e Root Node)
Consider Fig 2.0 Again :
10
/ \
8 12
/ \
7 9
/
5
Level Order traversal of this tree would be :
Level Order Traversal : 10,8,12,7,9,5
To accomplish this , idea I have used , is to use a queue . First insert root node in queue , then insert left child of it in queue , and insert right child of it in queue .
Loop while queue is not empty remove front element from queue , print it , and insert left and right children into queue .
See the complete Function to print tree in Level Order :
void printLevelOrder(struct NODE* root)
{
std::queue<struct NODE *> levelOrderQueue;
if(root == NULL)
return;
levelOrderQueue.push(root);
while(!levelOrderQueue.empty())
{
struct NODE * node = levelOrderQueue.front();
levelOrderQueue.pop();
std::cout<<node->data<<std::endl;
if(node->left != NULL)
levelOrderQueue.push(node->left);
if(node->right != NULL)
levelOrderQueue.push(node->right);
}
}
Insert Sorted Array into Balanced Binary search tree:
Here comes main topic of discussion. Its tricky and short part .The idea is to recursively find middle element of array , and insert it into binary search tree , using above function.
Lets say we have sorted array :
int arr[] = {1,2,3,4,5,6,7};
and we want to insert it into balanced binary search tree .
recursively find middle element of array and insert it into BST.Here middle element is calculated as
int mid = (low+high)/2.
Where low is lower bound and high is upper bound of array .
So in our case low is 0 and high is 6 (In C++ upper bound of array is size of array -1)
so mid will be 3.
So root of our tree would be : arr[3] , which turns out to be : 4
Now recursively devide the array in 2 subarrays : array from index low to mid-1 and array from index mid+1 to high . Apply the same procedure of finding middle element and insert that into tree.
Resulting tree would be :
4
/ \
2 6
/ \ / \
1 3 5 7
Fig 3.0
Wow what a balanced binary search tree.
Complete Function to insert sorted array into balanced binary search tree :
struct NODE* getBalancedBinaryTreeFromSortedArray(struct NODE*root,int* arr,int low,int high)
{
if(low<=high)
{
int mid = (int)((low+high)/2);
root = insertNode(root,arr[mid]);
root = getBalancedBinaryTreeFromSortedArray(root,arr,low,mid-1);
root = getBalancedBinaryTreeFromSortedArray(root,arr,mid+1,high);
}
return root;
}
Here int *arr is sorted array, low is lower bound of array (i.e 0) and high is upper bound of array ( which is size of array -1)
Use below statements to use it in your code :
int arr[] = {1,2,3,4,5,6,7};
root = getBalancedBinaryTreeFromSortedArray(root,arr,0,6);
For printing node of tree :
printLevelOrder(root);
Complete Working Program in C++ :
/**
* Author : Nitendra Bhosle
* Program : To Insert sorted array into balanced binary search tree
**/
#include <iostream>
#include <queue>
using namespace std;
struct NODE
{
int data;
struct NODE *left;
struct NODE *right;
};
struct NODE* insertNode(struct NODE *root,int val)
{
if(root == NULL)
{
root = new struct NODE;
root->data = val;
root->left = root->right = NULL;
return root;
}
else
{
if(val<root->data)
{
root->left = insertNode(root->left,val);
return root;
}
else
{
root->right = insertNode(root->right,val);
return root;
}
}
}
void printLevelOrder(struct NODE* root)
{
std::queue<struct NODE *> levelOrderQueue;
if(root == NULL)
return;
levelOrderQueue.push(root);
while(!levelOrderQueue.empty())
{
struct NODE * node = levelOrderQueue.front();
levelOrderQueue.pop();
std::cout<<node->data<<std::endl;
if(node->left != NULL)
levelOrderQueue.push(node->left);
if(node->right != NULL)
levelOrderQueue.push(node->right);
}
}
void printTree(struct NODE* root)
{
if(root != NULL)
{
printTree(root->left);
std::cout<<root->data<<std::endl;
printTree(root->right);
}
}
struct NODE* getBalancedBinaryTreeFromSortedArray(struct NODE*root,int* arr,int low,int high)
{
if(low<=high)
{
int mid = (int)((low+high)/2);
root = insertNode(root,arr[mid]);
root = getBalancedBinaryTreeFromSortedArray(root,arr,low,mid-1);
root = getBalancedBinaryTreeFromSortedArray(root,arr,mid+1,high);
}
return root;
}
int main()
{
struct NODE*root = NULL;
/*root = insertNode(root,10);
root = insertNode(root,5);
root = insertNode(root,1);
root = insertNode(root,7);
root = insertNode(root,3);
root = insertNode(root,2);
root = insertNode(root,12);
root = insertNode(root,11);
root = insertNode(root,13);*/
int arr[] = {1,2,3,4,5,6,7};
root = getBalancedBinaryTreeFromSortedArray(root,arr,0,6);
//printTree(root);
std::cout<<"\nLevel Order"<<std::endl;
printLevelOrder(root);
return 0;
}
No comments :
Post a Comment