Convert Sorted Array to Binary Search Tree

Python Help
1

LeetCode 108 Convert Sorted Array to Binary Search Tree

My solution is too long compared with the official solution. I wonder why it does not work. I tried to “print(root1.val)”, but the result is None. Any comment on my thinking process is welcome (Either modifying my code or telling me why I should not do the code)

def sortedArrayToBST_with_root(nums, root):
    n = len(nums)
    #if not nums:
    if n == 0:
        root = Node(None)
#        return
    elif n == 1:
        root = Node(None)
        root.val = nums[0]
#        return
    elif n == 2:
        root = Node(None)
        root.val = nums[1]
        root.left = Node(nums[0])
#        return
    else:
        mid = (n-1)//2
        root = Node(nums[mid])
        nums_left_half = nums[:mid]
        nums_right_half = nums[(mid+1):]
        root.left = Node(None)
        root.right = Node(None)
        sortedArrayToBST_with_root(nums_left_half, root.left)
        sortedArrayToBST_with_root(nums_right_half, root.right)

def sortedArrayToBST(nums):
    root = Node(None)
    sortedArrayToBST_with_root(nums, root)
    return root
    
nums = [-10,-3,0,5,9]
root1 = sortedArrayToBST(nums)
print(root1.val)
2

I don’t see your definition of the Node class. I’m assuming it has a
left, right abd value, and an __init__(self,value) initialiser.

Your code…

def sortedArrayToBST_with_root(nums, root):

You’re passing in the root, which you made in sortedArrayToBST(). So
everywhere you assign to root in this function discards the original
node passed to the function. Because of this, all your tree building is
done to a new root node, and the original is unchanged. So since it
starts with a value of None, it stays that way.

    n = len(nums)
    #if not nums:
    if n == 0:
        root = Node(None)

So drop this root= (replace with a pass statement) since root is
already initialised.

#        return
    elif n == 1:
        root = Node(None)

Drop this root= assignment.

        root.val = nums[0]
#        return
    elif n == 2:
        root = Node(None)

Drop this root= assignment.

        root.val = nums[1]
        root.left = Node(nums[0])
#        return
    else:
        mid = (n-1)//2

Are you sure you don’t just want n//2 here?

        root = Node(nums[mid])

Drop this root= assignment.

        nums_left_half = nums[:mid]
        nums_right_half = nums[(mid+1):]

You don’t need the parentheses here, though they do no harm.

        root.left = Node(None)
        root.right = Node(None)
        sortedArrayToBST_with_root(nums_left_half, root.left)
        sortedArrayToBST_with_root(nums_right_half, root.right)

def sortedArrayToBST(nums):
    root = Node(None)
    sortedArrayToBST_with_root(nums, root)
    return root

nums = [-10,-3,0,5,9]
root1 = sortedArrayToBST(nums)
print(root1.val)

The rest of the code looks superficially ok, though I have not run it.

Cheers,
Cameron Simpson cs@cskk.id.au

3

Thank you very much. My code can run now either for “mid = n//2” or “mid = (n-1)//2”. It seems to me that “mid = (n-1)//2” is even more faithful to the idea of “mid-point” since the first point is 0, and the last is (n-1). Is there a reason why people always use “n//2” rather than “(n-1)//2”?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None
        
def sortedArrayToBST_with_root(nums, root):   
    n = len(nums)
    if n == 0:
        pass  # do nothing
    elif n == 1:
        root.val = nums[0]
    elif n == 2:
        root.val = nums[1]
        root.left = Node(nums[0])
    else:
        mid = (n-1)//2
#        mid = n//2 
        root.val = nums[mid]
        nums_left_half = nums[:mid]
        nums_right_half = nums[(mid+1):]
        root.left = Node(None)
        root.right = Node(None)
        sortedArrayToBST_with_root(nums_left_half, root.left)
        sortedArrayToBST_with_root(nums_right_half, root.right)

def sortedArrayToBST(nums):
    root = Node(None)
    sortedArrayToBST_with_root(nums, root)
    return root
    
nums = [-10,-3,0,5,9]
root1 = sortedArrayToBST(nums)
print(root1.left.val)
4

My code can run now either for “mid = n//2” or “mid = (n-1)//2”. It
seems to me that “mid = (n-1)//2” is even more faithful to the idea of
“mid-point” since the first point is 0, and the last is (n-1). Is there
a reason why people always use “n//2” rather than “(n-1)//2”?

Aside from being visually simpler? I think because indices count from 0,
it felt like you were over subtracting. Let’s see:

for n in range(10):
mid = n // 2
print(n, ‘:’, mid, n-mid-1)
mid = (n-1) // 2
print(n, ‘:’, mid, n-mid-1)

It seems that neither is better, they just move the lopsidedness from
one side to the other:

>>> for n in range(10):
...     mid = n // 2
...     print(n, ':', mid, n-mid-1)
...     mid = (n-1) // 2
...     print(n, ':', mid, n-mid-1)
...
0 : 0 -1
0 : -1 0
1 : 0 0
1 : 0 0
2 : 1 0
2 : 0 1
3 : 1 1
3 : 1 1
4 : 2 1
4 : 1 2
5 : 2 2
5 : 2 2
6 : 3 2
6 : 2 3
7 : 3 3
7 : 3 3
8 : 4 3
8 : 3 4
9 : 4 4
9 : 4 4

Cheers,
Cameron Simpson cs@cskk.id.au

2 Likes
5

It can seem that way, but the thing to realize is that because you’re doing floor division, you’re already effectively subtracting 1 when the number of elements is odd.

If you have 8 elements, your mid will be 4, and if you have 9 elements, your mid will be… still 4. Discarding the fractional result pulls the mid downwards enough that, like @cameron said, if you also subtract 1 before you start then you’re just overcompensating (slightly) and flipping the imbalance from one side to the other.

For odd values of n, (n - 1) // 2 == n // 2, and for even values the tree is going to be imbalanced either way, so which way it tilts is meaningless.

1 Like