Convert Sorted Array to Binary Search Tree Leetcode Solution

In this post, we are going to solve the Convert Sorted Array to Binary Search Tree Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Convert Sorted Array to Binary Search Tree Leetcode Solution
Convert Sorted Array to Binary Search Tree Leetcode Solution

Problem

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

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.

Example 1:Convert Sorted Array to Binary Search Tree Leetcode Solution

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Convert Sorted Array to Binary Search Tree Leetcode Solution

Example 2:Convert Sorted Array to Binary Search Tree Leetcode Solution

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in a strictly increasing order.

Now, lets see the leetcode solution of Convert Sorted Array to Binary Search Tree Leetcode Solution.

Convert Sorted Array to Binary Search Tree Leetcode Solution in Python

class Solution:
  def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
    def build(l: int, r: int) -> Optional[TreeNode]:
      if l > r:
        return None

      m = (l + r) // 2
      return TreeNode(nums[m],
                      build(l, m - 1),
                      build(m + 1, r))

    return build(0, len(nums) - 1)

Convert Sorted Array to Binary Search Tree Leetcode Solution in CPP

class Solution {
 public:
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return build(nums, 0, nums.size() - 1);
  }

 private:
  TreeNode* build(const vector<int>& nums, int l, int r) {
    if (l > r)
      return nullptr;

    const int m = (l + r) / 2;
    return new TreeNode(nums[m],
                        build(nums, l, m - 1),
                        build(nums, m + 1, r));
  }
};

Convert Sorted Array to Binary Search Tree Leetcode Solution in Java

class Solution {
  public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
  }

  private TreeNode build(int[] nums, int l, int r) {
    if (l > r)
      return null;

    final int m = (l + r) / 2;
    return new TreeNode(nums[m],
                        build(nums, l, m - 1),
                        build(nums, m + 1, r));
  }
}

Note: This problem Convert Sorted Array to Binary Search Tree is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

Sharing Is Caring