This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/convert-sorted-array-to-height-balanced-binary-search-tree/.
Problem
Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.Examples
Input: 1 2 3 4 5 6 7 Output: 4 / \ 3 6 / \ / \ 3 4 6 7
Solutions
Method 1 - Take the array's middle element and insert it recursively- Pick up the middle element of the array
- Set it as the root
- Recursively build up left and right subtrees with lower and higher halves of the array
Here is the code in java:
public static BST sortedArrayToBST(int[] arr){ Node bst = new Node(); bst = sortedArrayToBST(arr, 0, arr.length-1, bst); return bt; } private static Node sortedArrayToBST(int[] arr, int start, int end) { if( start == end){ bst.insert(new Node(arr[start])); return; } else if(start > end) { return; } int middle = (start+end)/2; Node node = new Node(arr[middle]); //bst.insert(new Node(arr[middle])); node.left = sortedArrayToBST(arr, start, middle - 1); node.right = sortedArrayToBST(arr, middle+1, end); return node; }
Time complexity - O(n)
Space Complexity - O(1) (but if you internally think of recursion, it will be kind of O(n)
0 comments:
Post a Comment