This example to generate balanced binary search tree from an array.
A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
package com.omt.learn.algo; import com.omt.learn.algo.util.tree.TreeNode; import com.omt.learn.algo.util.tree.TreeUtil; import java.util.Arrays; /** * Created by dhpandya on 3/22/17. */ public class BSTFromArray { public static void main(String args[]) { //int a[] = {1, 5, 4, 2, 6, 3, 8, 7}; int a[] = {1, 3, 4, 2}; TreeNode tn = generateBST(a); TreeUtil.printTree(tn); } private static TreeNode generateBST(int a[]) { Arrays.sort(a); return generateBST(a, 1, a.length); } private static TreeNode generateBST(int a[], int start, int end) { if (start > end) { return null; } TreeNode tn = new TreeNode(); int mid = (start + end) / 2; tn.value = mid; tn.nodeName = String.valueOf(mid); tn.leftNode = generateBST(a, start, mid - 1); tn.rightNode = generateBST(a, mid + 1, end); return tn; } } |