Java solution using binary search - O(nlgn)


  • 0
    W

    A BST is balanced, if the middle element (in the sorted order) is at the root, so that half of the elements are on left of it and the other half on right.

    The same idea can be applied to construct a balanced binary tree.

    Let there be an auxiliary function that inserts a value into a BST with a given root. Now, the thing that matters is the order of selection to insert elements.

    Select the middle element from the array and insert it. Do this recursively for the left part and for the right part. That's all! Below is the code :-

    public class Solution {
        TreeNode root = null;
        public TreeNode sortedArrayToBST(int[] nums) {
            createBST(nums, 0, nums.length - 1);
            return root;
        }
        
        void createBST(int[] nums, int begin, int end) {
            if(begin > end)
                return;
            int mid = (begin + end) / 2;
            root = insert(root, nums[mid]);
            
            createBST(nums, begin, mid - 1);
            createBST(nums, mid + 1, end);
        }
        
        TreeNode insert(TreeNode root, int n) {
            if(root == null)
                return new TreeNode(n);
            if(n < root.val)
                root.left = insert(root.left, n);
            else
                root.right = insert(root.right, n);
            return root;
        }
    }
    

    'insert' is the auxiliary function to insert a given value into BST with the given root node.

    'createBST' is the main function. begin and end are the start and end index of the array in consideration.
    So, begin > end becomes the point of return from the recursion.

    We call 'insert' n times for each element. It takes logn time to insert into BST. So, overall O(nlgn)


  • -1
    S

    You are doing samething in 2 functions, you can name your createBST itself to isert and make it new TreeNode(n); instead of calling insert method. It just works.


  • 0
    M

    @saitemp said in Java solution using binary search - O(nlgn):

    You are doing samething in 2 functions, you can name your createBST itself to isert and make it new TreeNode(n); instead of calling insert method. It just works.

    I tried that and it didn't work. Please post the code.


Log in to reply
 

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