Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.
Example: Given sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5],which represents the following tree:
0 / \ -3 9 / / -10 5
Recursive Algorithm to Convert a Sorted List to a Balanced Binary Search Tree
A Balanced Binary Tree should have no more than 1 depth difference for any two sub trees. Given the sorted list, if we divide into half, the two parts (used to construct the left and right tree respectively), should have no more difference than 1. In this case, the balanced binary search tree is also the minimal height BST.
So, recursively, we pick the current middle as the current root, and recursively construct its left, and right subtrees.
The time complexity is O(N) where N is the number of the nodes in the sorted list – and also the number of the nodes in the final balanced binary search tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: if len(nums) == 0: return None mid = len(nums) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid+1:]) return root |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: if len(nums) == 0: return None mid = len(nums) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid+1:]) return root
See also: Recursive Algorithm to Convert a List to Binary Search Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Linked List Delete Last Occurrence of Value
Next Post: Binary Tree Algorithm: Checking Leaves in the Same Level