iframe-proxy | Sunbelt Computer Software

Repository navigation

History

# Time: O(n)

# Space: O(logn)

# Given an array where elements are sorted in ascending order,

# convert it to a height balanced BST.

# 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 sortedArrayToBST(self, num):

return self.sortedArrayToBSTRecu(num, 0, len(num))

@staticmethod

def perfect_tree_pivot(n):

"""

Find the point to partition n keys for a perfect binary search tree

"""

x = 1

# find a power of 2 <= n//2

# while x <= n//2: # this loop could probably be written more elegantly :)

# x *= 2

x = 1 << (n.bit_length() - 1) # use the left bit shift, same as multiplying x by 2**n-1

if x // 2 - 1 <= (n - x):

return x - 1 # case 1: the left subtree of the root is perfect and the right subtree has less nodes

else:

return n - x // 2 # case 2 == n - (x//2 - 1) - 1 : the left subtree of the root

# has more nodes and the right subtree is perfect.

def sortedArrayToBSTRecu(self, num, start, end):

if start == end:

return None

mid = start + self.perfect_tree_pivot(end - start)

node = TreeNode(num[mid])

node.left = self.sortedArrayToBSTRecu(num, start, mid)

node.right = self.sortedArrayToBSTRecu(num, mid + 1, end)

return node

if __name__ == "__main__":

num = [1, 2, 3]

result = Solution().sortedArrayToBST(num)

print result.val

print result.left.val

print result.right.val

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Repository navigation

convert-sorted-array-to-binary-search-tree.py

convert-sorted-array-to-binary-search-tree.py

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

convert-sorted-array-to-binary-search-tree.py

Latest commit

History

convert-sorted-array-to-binary-search-tree.py

File metadata and controls