leetcode Question 23: Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


Because the requirement "height balanced", this problem becomes relative easy.
Just recursively use the middle element in the array as the root node of the current tree(sub tree).


 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
class Solution {

    TreeNode* cbst(vector<int> &num, int st, int ed){
        if (st>ed){
            return NULL;
            int mid = st+(ed-st)/2;
            TreeNode *bst=new TreeNode(num[mid]);
            bst->left = cbst(num,st,mid-1);
            bst->right = cbst(num,mid+1,ed);
            return bst;

    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (num.size()==0){return NULL;}
        return cbst(num,0,num.size()-1);


# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param num, a list of integers
    # @return a tree node
    def bst(self, num, st, ed):
        if st > ed:
            return None
        mid = st + (ed - st)/2
        left = self.bst(num, st, mid - 1)
        root = TreeNode(num[mid])
        right = self.bst(num, mid + 1, ed)
        root.left = left
        root.right = right
        return root
    def sortedArrayToBST(self, num):
        n = len(num)
        if n == 0:
            return None
        return self.bst(num, 0, n-1)

1 comment:

  1. You usually have Java code for the algorithms, solution is trivial still thought I'd comment in mine

    public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
    if(nums.length==0) return null;
    return createBST(0,nums.length-1,nums);

    private TreeNode createBST(int start, int end, int[] nums) {
    if(start>end) return null;
    else {
    int mid=start+ end >>1;
    TreeNode subTree=new TreeNode(nums[mid]);
    return subTree;

    if the question asked to create a complete binary tree i.e. all leaf nodes must be as far left as possible could you help as to how to approach that?