codebytes: Constructing a minimum height BST with elements from a sorted array.
Constructing a minimum height BST with elements from a sorted array.
Q. Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.
Algorithm:
1. Pass the array reference, starting index (s) and end index (e) recursively.
2. Calculate mid = (e+s)/2
3. Construct a new Node with array[mid] as the value.
4. Now node.left = (array, s, mid-1)
5. node.right = (array, mid+1, e)
6. Return this node.
7. Returning condition during recursion:
if(s > e) we must return null (no element to be placed there)
if(s==e) return new Node(array[s])
Algorithm:
1. Pass the array reference, starting index (s) and end index (e) recursively.
2. Calculate mid = (e+s)/2
3. Construct a new Node with array[mid] as the value.
4. Now node.left = (array, s, mid-1)
5. node.right = (array, mid+1, e)
6. Return this node.
7. Returning condition during recursion:
if(s > e) we must return null (no element to be placed there)
if(s==e) return new Node(array[s])
Read full article from codebytes: Constructing a minimum height BST with elements from a sorted array.
No comments:
Post a Comment