Python program to construct a complete binary tree from given array.
Description:
To create a binary tree from an array, we will use level order fashion for insertion of elements in the tree.
Here is an example to make you understand clearly...
Array :- arr =[1,2,3,4,5,6,7]
Expected Output:
So from this example we can see that, if parent node is at the index i in the array then the left child
of that node is at the index (2*i+1) and right child is at index(2*i+2) in the array. Using this concept, we can easily insert the left and right nodes by choosing its parent node.
We will insert the first element of array as the root of the tree at level 0 and start traversing the array and for every node i we will insert its both child's left and right in the tree.
Program:
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Function to insert nodes in level order
def levelOrderInsertion(arr, root, i, n):
# Base case for recursion
if i < n:
temp = newNode(arr[i])
root = temp
# insert left child
root.left = levelOrderInsertion(arr, root.left, 2 * i + 1, n)
# insert right child
root.right = levelOrderInsertion(arr, root.right, 2 * i + 2, n)
return root
# Function to print tree nodes in
# PreOrder fashion
def preOrder(root):
if root!=None:
preOrder(root.left)
preOrder(root.right)
print(root.data,end=" ")
# Driver Code
if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6,7]
n = len(arr)
root = None
root = levelOrderInsertion(arr, root, 0, n)
preOrder(root)
Output:
4 5 2 6 7 3 1
>>>
Comments