Convert sorted array to Binary Search Tree (Java) stack overflow exception

Question

This is a program for converting an array, where elements are sorted in ascending order, to a height balanced BST.

I input five element, pass them to an array, sort the array and use methods.

It produces this error:

Exception in thread "main" java.lang.StackOverflowError
    at Solution.sortedArrayToBST(Node.java:26)

How do I fix this error?

import java.util.*;

class Node {
    int val;
    Node left;
    Node right;

    Node(int x) {
        val = x;
    }
}

class Solution {

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

        return sortedArrayToBST(num, 0, num.length - 1);
    }

    public Node sortedArrayToBST(int[] num, int start, int end) {

        int mid = (start + end) / 2;
        Node root = new Node(num[mid]);
        root.left = sortedArrayToBST(num, start, mid - 1);
        root.right = sortedArrayToBST(num, mid + 1, end);

        return root;
    }

    public static void main(String[] args) {

        Solution sol = new Solution();

        Scanner input = new Scanner(System.in);
        int[] numbers = new int[5];

        System.out.println("Please enter numbers");
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = input.nextInt();
        }

        // sorting
        for (int j = 0; j<numbers.length; j++) {
            for (int k = 0; k < numbers.length; k++){
                if (numbers[j] < numbers[k]) {
                    int buffer = numbers[j];
                    numbers[j] = numbers[k];
                    numbers[k] = buffer; 
                }
            }
        }

        sol.sortedArrayToBST(numbers, 0, 5);
        sol.sortedArrayToBST(numbers);
    }

}

SMA · Accepted Answer · 2014-11-02 14:03:39Z

0

sortedArrayToBST with array calls sortedArrayToBST with 3 parameter (which in turn calls same method with one parameter) and you never get out of it.

You are sending the same array of same size again and again to sortedArrayToBST with one parameter. Instead you should create new array by breaking it into two (low-mid and mid+1 to high)

answered Nov 2, 2014 at 14:03

SMA

37.2k8 gold badges53 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user5310464 · Accepted Answer · 2015-09-07 20:58:35Z

0

The method sortedArrayToBST(num, start, end) does not have a termination condition that is why it never ends are you are getting StackOverFlow error. You need to add a condition in the start of the method: if(start > end) return null. You can check this Youtube video on Sorted Array to BST problem: Create a balanced binary search tree from a sorted array

answered Sep 7, 2015 at 20:58

user5310464

Collectives™ on Stack Overflow

Convert sorted array to Binary Search Tree (Java) stack overflow exception

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related