Python program to construct a complete binary tree from a given array














































Python program to construct a complete binary tree from a given array



Description:

This python program involves constructing a complete binary tree from a given array in level order fashion. A binary tree is a complete binary tree if all leve will be filled in the tree level wise starting from level 0. Task is very simple. It can be done in python the following way.

Example :

>>> print(build([3, 4, 5, 6, 7, 8, 9, 13, 14]))

          __3__
         /     \
     ___4       5
    /    \     / \
  _6      7   8   9
 /  \
13   14


Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Node:
    def __init__(self, data):
        self.value = data
        self.left = None
        self.right = None


class BST:
    def __init__(self, root):
        self.root = root

    def in_order(self, start, traversal):
        if start:
            traversal = self.in_order(start.left, traversal)
            traversal.append(start.value)
            traversal = self.in_order(start.right, traversal)
        return traversal


def arr_to_tree(arr, root, i, n):
    if i < n:
        temp = Node(arr[i])
        root = temp
        root.left = arr_to_tree(arr, root.left, 2*i+1, n)
        root.right = arr_to_tree(arr, root.left, 2*i+2, n)
    return root


def main():
    li = [9, 2, 7, 4, 0, 6, 8, 8, 2, 3]

    root = None
    root = arr_to_tree(li, root, 0, len(li))

    bst = BST(root)
    print(bst.in_order(root, []))


if __name__ == '__main__':
    main()


Output:

apoorv@apoorv:~/Desktop/classes_py/I_ship/binary_tree_DS$ python arr_to_complete_bt.py 
[8, 4, 2, 2, 3, 0, 3, 9, 6, 7, 8]

Visualization for more clarity:

>>> print(build([9, 2, 7, 4, 0, 6, 8, 8, 2, 3]))

        ____9__
       /       \
    __2__       7
   /     \     / \
  4       0   6   8
 / \     /
8   2   3

>>> 



More Articles of Apoorv Patne:

Name Views Likes
Python program to count number of spaces in a file 958 16
Python program to check whether all leaves of a binary tree are at same level 691 20
Python program to print unique words from a file 2114 15
Python program to find mirror image of a tree using recursive and iterative approach 949 23
Python program to understand deletion in Red-Black Trees 4368 18
Usage of dictionaries in python 1229 28
Python program to work on binary trees using binarytree module 994 12
Python program to write to a file 693 20
Python program to demonstrate usage of config-reader framework using configparser module 990 17
Python program to create tree from given in order and pre order traversal 676 18
Python program to convert Sorted Array to binary search tree 947 13
Python program to find the level-order traversal for a given binary tree 1095 21
Python program to remove punctuations from a given string. 689 21
Python program to find the minimum depth of a binary tree 820 25
Python program to merge files 986 20
Python program to find in-order predecessor and successor with and without recursion 2248 12
Python program to shuffle lines in a file 1666 19
Python program to encrypt a password using encryption 1007 18
Python program to compare strings 890 29
Python send mail via command line argument 674 19
Python program to elaborate and understand memory management 941 21
Python article to demonstrate the usage of help() and dir() methods 984 19
Tset 660 13
Python program to construct a complete binary tree from a given array 3877 23
Python program to encrypt and decrypt contents from a file via command line 1640 24
Python program to count number of lines using different methods 654 19
Python program to perform copy, concatenation and reverse operations on strings 663 20
Python program to find maximum number using ternary operations 750 17
Python program to find the mirror of a given node in a binary tree 828 17
Python program to convert decimal to its binary, octal and hexadecimal equivalent 777 27
Python program to extract and create a 7z file 2172 18
Python program to find all paths from root to leaves 1104 24
Python program to compute HCF and LCM of given numbers 929 26
Python program to read a fiel 661 19
Python program to find size of tree with and without recursion 714 15
Python program to sort an integer array using quick sort, radix sort, merge sort, bucket sort and other algorithms 885 16
Python birthday reminder application using SMTP and SQLAlchemy 3020 23
Python program to append content of one text file to another 1126 13
Python program to convert a binary number to its equivalent decimal, octal and hexadecimal equivalent. 983 23
Python program to understand Red-Black trees and insert nodes to it 2879 23
Python program to understand linked lists and its operations (fully tested) 889 12
Python program to check if two strings are a rotation of each other 835 14

Comments