CODEWITHSUNDEEP
algorithmsortingtreebinary-treebinary-search-tree
Ege
Ege

Reputation: 941

Insert sorted array into binary search tree

I want to implement an algorithm that inserts sorted arrays into binary search trees but I don't want ending up with a tree that only grows to one side.

Do you have any ideas?

Thanks.

Upvotes: 8

Views: 12457

Answers (3)

F.Z
F.Z

Reputation: 93

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;
    }
}

Upvotes: 4

Bernhard Barker
Bernhard Barker

Reputation: 55589

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

  1. Construct a node for the middle element in the array and return it
    (this will be the root in the base case).
  2. Repeat from 1. on the left half of the array, assigning the return value to the left child of the root.
  3. Repeat from 1. on the right half of the array, assigning the return value to the right 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.

Upvotes: 11

wildplasser
wildplasser

Reputation: 44240

Insert them in 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;
}

Upvotes: 0

Related Questions