w3resource

Python Binary Search Tree: Convert a array to Binary Search Tree (BST)


5. Array to Height Balanced BST

Write a Python program to convert a given array of elements to a height balanced Binary Search Tree (BST).

Note: The selection sort improves on the bubble sort by making only one exchange for every pass through the list.

Sample Solution:

Python Code:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def array_to_bst(array_nums):
    if not array_nums:
        return None
    mid_num = len(array_nums)//2
    node = TreeNode(array_nums[mid_num])
    node.left = array_to_bst(array_nums[:mid_num])
    node.right = array_to_bst(array_nums[mid_num+1:])
    return node

def preOrder(node): 
    if not node: 
        return      
    print(node.val)
    preOrder(node.left) 
    preOrder(node.right)   

array_nums = [1,2,3,4,5,6,7]

print("Original array:")
print(array_nums)
result = array_to_bst(array_nums)
print("\nArray to a height balanced BST:")
print(preOrder(result))

Sample Output:

Original array:
[1, 2, 3, 4, 5, 6, 7]

Array to a height balanced BST:
4
2
1
3
6
5
7
None

Flowchart:

Flowchart: Convert a array to Binary Search Tree.

For more Practice: Solve these Related Problems:

  • Write a Python program to convert a sorted array into a height balanced BST and then perform a pre-order traversal to display the structure.
  • Write a Python script to build a height balanced BST from an array and then compare the heights of its left and right subtrees for every node.
  • Write a Python program to create a height balanced BST from a sorted array and then calculate and print its balance factor at the root.
  • Write a Python function to generate a height balanced BST from a sorted list and then serialize the tree into a list using level order traversal.

Go to:


Previous: Write a Python program to delete a node with the given key in a given Binary search tree (BST).
Next: Write a Python program to find the kth smallest element in a given a binary search tree.

Python Code Editor:

Contribute your code and comments through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.