0
$\begingroup$

What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?

Could you, please, check my reasoning. Is it correct?

Here is my algorithm for solving the problem:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return SortedArrayToBST(nums, 0, nums.Length - 1);
    }
    
    private TreeNode SortedArrayToBST(int[] nums, int low, int high) {
        if(high < low) {
            return null;
        }
        
        if(low == high) {
            return new TreeNode(nums[low]);
        }
        
        int center = low + (high - low)/2;
        
        return new TreeNode(
            nums[center],
            SortedArrayToBST(nums, low, center - 1),
            SortedArrayToBST(nums, center + 1, high)
        );
    }
}

The space complexity in this case will be equal to the amount of the call stacks + O(1). So, we need to find the amount of stacks, given that the nums.Length == n;

Each time there is a recursive call the array is split in two. That means that there will be as many stacks as we can divide n by two, until it is equal to 0. But also, since for each of the two splittings we run the recusion we need to multiply that by 2. That brings us to the O(2*log(n)) or simply O(log(n)) space complexity.

UPDATE

We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors." - the answer to the question What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution? is definitely not yes/no.

Can you edit your post to ask about a specific conceptual issue you're uncertain about? Sure I did. Let me repeat my conceptual issue: What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?.

As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. I am not the only one who needs to know the space complexity of the conversion.

Coding questions and questions about code or that are specific to a particular programming language are off-topic here. I don't have coding questions.

Not everyone here knows Java. We would prefer to see concise pseudocode, not Java code. Not everyone knows pseudocode. E.g. I don't know it.

$\endgroup$
3
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Mar 15, 2021 at 5:56
  • $\begingroup$ Coding questions and questions about code or that are specific to a particular programming language are off-topic here. Not everyone here knows Java. We would prefer to see concise pseudocode, not Java code. $\endgroup$
    – D.W.
    Mar 15, 2021 at 5:57
  • $\begingroup$ @D.W., thanks for your time. I updated my question to address all your comments. $\endgroup$
    – some1 here
    Mar 15, 2021 at 17:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.