Insert sorted array into binary search tree

Question

I want to implement an algorithm that inserts sorted arrays into binary search trees, but I don't want a tree that only grows to the side to end.

Do you have any ideas?

Thanks.

Answer 1

This should give you a balanced tree (in O (n)):

• Build a node for the middle element in the array and return it
  (this will be the root in the base case).
• Repeat from 1. in the left half of the array, assigning a return value to the left child of the root.
• Repeat from 1. in the right half of the array, assigning the return value to the correct child of the root.

Java-like code:

TreeNode sortedArrayToBST(int arr[], int start, int end) { if (start > end) return null; // same as (start+end)/2, avoids overflow. int mid = start + (end - start) / 2; TreeNode node = new TreeNode(arr[mid]); node.left = sortedArrayToBST(arr, start, mid-1); node.right = sortedArrayToBST(arr, mid+1, end); return node; } TreeNode sortedArrayToBST(int arr[]) { return sortedArrayToBST(arr, 0, arr.length-1); } 

Code derived from here .

Answer 2

 public class SortedArrayToBST { public TreeNode sortedArrayToBST(int[] num) { if (num == null) { return null; } return buildBST(num, 0, num.length - 1); } private TreeNode buildBST(int[] num, int start, int end) { if (start > end) { return null; } int mid = start + (end - start) / 2; TreeNode root = new TreeNode(num[mid]); TreeNode left = buildBST(num, start, mid - 1); TreeNode right = buildBST(num, mid + 1, end); root.left = left; root.right = right; return root; } } 

Answer 3

Insert them into a pseudo-random order, like here:

 #include <stdio.h> int array[] = {1,2,3,4,5,6,7,8,9,10}; #define COUNT 10 #define STEP 7 /* must be relatively prime wrt COUNT */ #define START 5 /* not important */ int main(void) { unsigned idx; idx=START; while(1) { printf("[%u] = %u\n", idx, array[idx] ); // do_insert(array[idx] ); idx = (idx + STEP ) % COUNT; if (idx == START) break; } return 0; }