Convert Sorted Array to Binary Search Tree

Question

I am working on "Convert Sorted Array to Binary Search Tree With Minimal Height", which asked:

Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height.

I am not able to find why my recursive does not stop as I expected. It should stop when 7 passed, and will not print out 7 again. I also found a similar answer, it looks like used same strategy as mine, but it works fine. (I don't think my question is duplicate as those questions listed above, but I still want to thank you to link them for me. They gave me more idea to solve my problem.)

My code is below:

public TreeNode sortedArrayToBST(int[] A) {  
    int len = A.length;
    if(len <= 0){
        return null;
    }

    TreeNode root = new TreeNode(A[(len - 1) / 2]);
    if(len == 1){
        return root;
    }
    else{
        helper(root, A, 0, len - 1);
    }
    return root;
}

public void helper(TreeNode root, int[] A, int leftPoint, int rightPoint){
    if((rightPoint - leftPoint) <= 0){
        return;
    }

    int mid = (rightPoint - leftPoint) / 2 + leftPoint;
    int leftChild = (mid - 1 - leftPoint) / 2 + leftPoint;
    int rightChild = (rightPoint - (mid + 1)) / 2 + mid + 1;

    TreeNode left = new TreeNode(A[leftChild]);
    root.left = left;

    TreeNode right = new TreeNode(A[rightChild]);
    root.right = right;

    helper(root.left, A, leftPoint, mid - 1);
    helper(root.right, A, mid + 1, rightPoint);
    return;
}

When I run it, I got this.

My input
[1,2,3,4,5,6,7,8]

My output
{4,2,6,1,3,5,7,#,#,#,#,#,#,7,8}

Expected
{4,2,6,1,3,5,7,#,#,#,#,#,#,#,8}

Why does it have duplicate 7 at right side? As 7 has been used, it should be kicked out.

And I found my idea is similar with the following answer:

public TreeNode sortedArrayToBST(int[] A) {  
    // write your code here
    int len = A.length;
    if(len <= 0){
        return null;
    }
    TreeNode root = helper1(A, 0, len - 1);
    return root;
}

public TreeNode helper1(int[] A, int low, int high){
    if(low > high){
        return null;
    }
    int mid = (high + low) / 2;
    TreeNode root = new TreeNode(A[mid]);
    root.left = helper1(A, low, mid - 1);
    root.right = helper1(A, mid + 1, high);
    return root;
}

Have you tried debugging? You are most likely to find the problem. — luizfzs, Jul 12 '17 at 13:34
I tried debugging and I ran it on paper, too. I am surely confused now... — X. Amanda, Jul 12 '17 at 13:37
The similar answer works, but mine doesn't. I want to know why... — X. Amanda, Jul 12 '17 at 13:46
[What does your step debugger tell you?](http://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — , Jul 12 '17 at 16:08
Please read [How do I ask a good question?](http://stackoverflow.com/help/how-to-ask) before attempting to ask more questions. — , Jul 12 '17 at 16:08
Please read [Why is “Can someone help me?” not an actual question?](https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question) before attempting to ask more questions. — , Jul 12 '17 at 16:08
Please post solutions as answers not as updates to the question. This is to avoid confusion. I appreciate it has been marked as a duplicate but please do refrain from adding in solutions into the question. Thank you. — Bugs, Jul 13 '17 at 06:17

xenteros · Answer 1 · 2017-07-12T13:51:17.553

Let's have the following array:

[1,2,3,4,5,6,7]

The expected BST is:

       4
    2     6
  1   3  5  7

To achieve that, we can go in the following way:

for (int i = 0; i < logn; i++) {
    //insert ith level
}

To make things easier, lets find min n, so n > array.length and n = 2^k.

On ith level, starting from i = 0 we've got:

n/2^(i+1), 3*n/2^(i+1), 5*n/2^(i+1)...

The numbers above, are all indexes in the array.

public TreeNode sortedArrayToBST(int[] A) {  
    int len = A.length;
    if(len <= 0){
        return null;
    }

    int n = 1;
    int i = 0;
    while (n < len) {
        n *= 2;
        i++;
    }

    TreeNode root = new TreeNode(A[n/2]);

    for (int j = 1; j < i; j++) {
        insert(root, j, n, A);
    }
}

private void insert(TreeNode root, int j, int n, int[] A) {

    int helper = n/Math.pow(2, j+1);
    for (int i = 1; i <= Math.pow(2, j); i ++) {
        root.add(A[i*helper]);
    }
}

Method which adds new node. I don't know how you called it – xenteros Jul 12 '17 at 15:55 — xenteros, Jul 12 '17 at 15:55

score 0 · Answer 2 · answered Jul 12 '17 at 16:06

This might work

public TreeNode sortedArrayToBST(int[] A) {
    if (A.length() == 0)
        return null;

    return helper1(A, 0, A.length - 1);
}
public TreeNode helper1(int[] A, int low, int high) {
    if (low > high)
        return null;

    // Binary Search
    int mid = low + (high - low)/2;
    TreeNode root = new TreeNode(A[mid]);

    root.left = helper1(A, low, mid - 1);
    root.right = helper1(A, mid + 1, high);

    return root;
}

Convert Sorted Array to Binary Search Tree

2 Answers2