Convert Sorted Array to Binary Search Tree

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)
``````

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.

``````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

``````#        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

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)
``````

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

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