# My java solution, with quite some tricks in calculating the size of binary tree

• it's been a good exercise to familiarize with the size properties of binary tree

``````/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if (num.length == 0) return null;
return recursive(num, 0, num.length-1);
}

public TreeNode recursive(int []num, int start, int end) {
int len = end -start +1;
int fullSubTreeSize = (lowPow(len+1)>>1 )-1;

int bottomRowSize = fullSubTreeSize +1;
int left; int right;
if (len > fullSubTreeSize * 2 + 1  + bottomRowSize) {
left = fullSubTreeSize  + bottomRowSize;
right = len - fullSubTreeSize - bottomRowSize - 1;
}   else  {
left = fullSubTreeSize + (len - fullSubTreeSize*2 -1 );
right = fullSubTreeSize;
}

TreeNode n = new TreeNode(num[start + left]);
if (left > 0)
n.left = recursive(num, start, start+left-1);
if (right>0)
n.right = recursive(num, start+left+1, end);

return n;
}

// find the largest power of 2 , that is smaller or equal to the given number l
int lowPow(int l) {
l |= l>>1;
l |= l>>2;
l |= l>>4;
l |= l>>8;
l |= l>>16;
l+=1;
l = l >> 1;

return l;
}
}``````

• I used more complex calculation than (size/2) , because I constructed binary trees similar to a priority queue, where every layer is complete except for the last layer, and all the nodes on the last layer is left-adjusted. given a 9-node array, the size/2 approach would give a left subtree with 4 nodes, and a right one with 4 nodes, so both subtrees are not complete.

OJ seems to be ok as long as the 2 subtrees are not different by 1 level. but it would be nice to have a definitive answer

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.