Convert Sorted Array to Binary Search Tree LeetCode Solutions

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Microsoft Oracle VMware YahooViews 3536

Problem Statement

Convert Sorted Array to Binary Search Tree LeetCode Solutions says given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Convert Sorted Array to Binary Search Tree LeetCode Solutions

Example:

Test Case 1:

Input:

nums = [2, 3, 4, 5, 6, 7, 8, 9]

Output:

[4, 2, 8, null, 3, 6, 9, null, null, 5, 7]

Explanation:

for the test case, we can convert the array into a tree as shown below. As seen in the figure, the maximum difference between the depth of 2 subtrees of each node is 1.

Convert Sorted Array to Binary Search Tree LeetCode Solutions

Approach

Idea:

We can think of various tree traversal techniques and their properties. We know InOrder traversal of a Binary  Search Tree gives the number in sorted order. So the given input is basically the InOrder traversal of the Binary Search Tree we need to create. Here the main key to solving the problem is to make TreeNode out of the middle number and pass on the left half of the array to form a Left tree and the right half of the array to form a right tree.

Code

Java Program for Convert Sorted Array to Binary Search Tree

class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
      if (num.length == 0) {
          return null;
      }
      TreeNode root = arrayToTreeConverter(num, 0, num.length - 1);
      return root;
    }

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

C++ Program for Convert Sorted Array to Binary Search Tree

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
      if (nums.size() == 0) {
          return NULL;
      }
      TreeNode* root = arrayToTreeConverter(nums, 0, nums.size() - 1);
      return root;
    }
    TreeNode* arrayToTreeConverter(vector<int>& nums, int low, int high) {
      if (low > high) { 
        return NULL;
      }
      int mid = (low + high) / 2;
      TreeNode* root = new TreeNode(nums[mid]);
      root->left = arrayToTreeConverter(nums, low, mid - 1);
      root->right = arrayToTreeConverter(nums, mid + 1, high);
      return root;
    }
};

Complexity Analysis for Convert Sorted Array to Binary Search Tree LeetCode Solution

Time Complexity

Here we are traversing each node exactly once. So the time complexity is O(n). (n is no of nodes in the tree)

Space Complexity

Here the space complexity is actually the recursion stack which for a balanced tree should be O(logn). So the space complexity is O(logn).

Reference: https://en.wikipedia.org/?title=Inorder_traversal&redirect=yes

Translate »