Given a sorted array, how do we create binary search which height balanced.
For example the array [1,2,3,4,5] must be transformed to the following binary tree
3
/
2 4
/
1 5
We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.
How do we do it?
The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.
Here is the C++ code.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <queue> | |
using namespace std; | |
//Binary tree node type | |
struct TreeNode | |
{ | |
int val; | |
TreeNode *left, *right; | |
TreeNode(int v):val(v),left(NULL), right(NULL) | |
{ | |
} | |
}; | |
//Binary search tree insert procedure for creating binary tree to test | |
TreeNode* insert(TreeNode * root, int data) | |
{ | |
if( root == NULL ) | |
{ | |
root = new TreeNode(data); | |
return root; | |
} | |
if( data < root->val ) | |
root->left = insert( root->left, data ); | |
else | |
root->right = insert( root->right, data ); | |
return root; | |
} | |
TreeNode * create_balanced_tree(int arr[], int l, int h) | |
{ | |
if( l <= h ) | |
{ | |
int m = (l+h)/2; | |
TreeNode *root = new TreeNode(arr[m]); | |
root->left = create_balanced_tree(arr,l,m-1); | |
root->right = create_balanced_tree(arr,m+1,h); | |
return root; | |
} | |
return NULL; | |
} | |
void print_level_order(TreeNode *root) | |
{ | |
if( root == NULL ) | |
return; | |
queue<TreeNode *> q; | |
q.push(root); | |
while( !q.empty()) | |
{ | |
TreeNode *temp = q.front(); | |
q.pop(); | |
cout << temp->val << " "; | |
if( temp->left ) | |
q.push(temp->left); | |
if( temp->right ) | |
q.push(temp->right); | |
} | |
} | |
void Test() | |
{ | |
int arr[] = {1,2,3,4,5,6,7}; | |
TreeNode *root = create_balanced_tree(arr, 0, 6); | |
print_level_order(root); | |
} | |
int main() | |
{ | |
Test(); | |
return 0; | |
} |