Question

PYTHON CODING

Using the structural node and methods discussed in Binary Search Tree below

# Binary Tree Node structure

class Node:

# Constructor to create a new node

def __init__(self, data):

self.data = data

self.left = None

self.right = None

class BSTree():

def __init__(self, rootdata):

self.root = Node(rootdata)

  

def insert(self, data, cur_node):

if data < cur_node.data:

if cur_node.left == None:

cur_node.left = Node(data)

else:

self.insert(data, cur_node.left)

  

elif data > cur_node.data:

if cur_node.right == None:

cur_node.right = Node(data)

else:

self.insert(data, cur_node.right)

else:

print("Duplicate value!")

create a method for the Binary Search Tree that takes an unsorted input list and constructs a Binary Search Tree based on its values. Any duplicate value will only appear once on the tree. This method outputs a Binary Search Tree structure (not an enumeration of the tree). Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.Illustrate the performance of method enumerating the tree using level-order-traversal method on 3 examples of sizes (10, 20 and 30) and on the data below.

datalist= [199, 666, 930, 751, 120, 411, 534, 716, 134, 379, 908, 97, 740, 904, 575, 437, 983, 835, 931, 768, 405, 544, 553, 821, 160, 312, 228, 324, 675, 622, 768, 312, 310, 18, 558, 170, 842, 214, 545, 857, 6, 71, 421, 909, 908, 377, 488, 837, 884, 382, 1, 654, 207, 751, 459, 450, 431, 462, 40, 926, 304, 594, 966, 386, 760, 39, 297, 557, 125, 327, 278, 328, 937, 195, 346, 419, 953, 681, 203, 173, 807, 710, 428, 415, 601, 258, 981, 464, 568, 546, 308, 883, 431, 948, 529, 55, 651, 73, 411, 719, 172, 43, 249, 695, 636, 603, 447, 652, 211, 736, 923, 27, 198, 427, 154, 572, 671, 314, 25, 428, 900, 930, 378, 806, 281, 805, 627, 748, 23, 961, 244, 587, 352, 939, 880, 69, 52, 702, 856, 990, 19, 743, 132, 793, 279, 500, 776, 921, 583, 487, 638, 753, 209, 870, 506, 995, 691, 743, 501, 831, 549, 369, 718, 780, 17, 636, 217, 486, 548, 500, 381, 116, 84, 683, 908, 151, 633, 404, 4, 426, 92, 614, 851, 714, 90, 789, 441, 985, 539, 470, 891, 384, 962, 259, 938, 211, 683, 560, 630, 893, 106, 841, 974, 114, 239, 896, 796, 524, 896, 974, 583, 729, 577, 863, 696, 530, 670, 467, 841, 401, 209, 596, 862, 702, 21, 219, 902, 271, 293, 350, 357, 182, 179, 909, 874, 769, 192, 39, 7, 487, 571, 155, 565, 231, 36, 544, 443, 24, 596, 570, 129, 585, 529, 557, 833, 270, 241, 732, 569, 839, 762, 881, 177, 149, 413, 806, 545, 591, 721, 289, 453, 53, 470, 215, 480, 218, 787, 915, 532, 626, 18, 349, 216, 338, 572, 979, 939, 76, 55, 49, 727, 524, 68, 403, 941, 234, 85, 991, 698, 561]

Answer 1

Let us first consider the code which is already there in the question

THE Binary Search Tree created will be something like this -

Clearly if there are N nodes in the array and if the BST created is unbalanced i.e all the nodes are only on one side then while inserting each node in the Binary SearchTree we are going to traverse the whole BST everytime which means we will traverse all N nodes for each node N in array which will make our complexity equal to log(n*n).

That means in the Time complexity is O(n^2).

Now we will add the method which will do level order traversal and then we will discuss the enumeration

The final code will be

# Binary Tree Node structure

class Node:

# Constructor to create a new node

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

class BSTree():

    def __init__(self, rootdata):

        self.root = Node(rootdata)

    def insert(self, data, cur_node):

        if data < cur_node.data:

            if cur_node.left == None:

                cur_node.left = Node(data)

            else:

                self.insert(data, cur_node.left)

        elif data > cur_node.data:

            if cur_node.right == None:

                cur_node.right = Node(data)

            else:   

                self.insert(data, cur_node.right)

        else:

            print("Duplicate value!")

temp=[]

# Function to add all nodes of a given level from left to right

def printLevel(root, level):

    # base case

    if root is None:

        return False

    if level == 1:

        temp.append(root.data)

        # return true if at-least one node is present at given level

        return True

    left = printLevel(root.left, level - 1)

    right = printLevel(root.right, level - 1)

    return left or right

# Function to traverse level order traversal of given binary tree

def levelOrderTraversal(root):

    # start from level 1 -- till height of the tree

    level = 1

    # run till printLevel() returns false

    while printLevel(root, level):

        level = level + 1

    

arr = [199, 666, 930, 751, 120, 411, 534, 716, 134, 379, 908, 97, 740, 904, 575, 437, 983, 835, 931, 768, 405, 544, 553, 821, 160, 312, 228, 324, 675, 622, 768, 312, 310, 18, 558, 170, 842, 214, 545, 857, 6, 71, 421, 909, 908, 377, 488, 837, 884, 382, 1, 654, 207, 751, 459, 450, 431, 462, 40, 926, 304, 594, 966, 386, 760, 39, 297, 557, 125, 327, 278, 328, 937, 195, 346, 419, 953, 681, 203, 173, 807, 710, 428, 415, 601, 258, 981, 464, 568, 546, 308, 883, 431, 948, 529, 55, 651, 73, 411, 719, 172, 43, 249, 695, 636, 603, 447, 652, 211, 736, 923, 27, 198, 427, 154, 572, 671, 314, 25, 428, 900, 930, 378, 806, 281, 805, 627, 748, 23, 961, 244, 587, 352, 939, 880, 69, 52, 702, 856, 990, 19, 743, 132, 793, 279, 500, 776, 921, 583, 487, 638, 753, 209, 870, 506, 995, 691, 743, 501, 831, 549, 369, 718, 780, 17, 636, 217, 486, 548, 500, 381, 116, 84, 683, 908, 151, 633, 404, 4, 426, 92, 614, 851, 714, 90, 789, 441, 985, 539, 470, 891, 384, 962, 259, 938, 211, 683, 560, 630, 893, 106, 841, 974, 114, 239, 896, 796, 524, 896, 974, 583, 729, 577, 863, 696, 530, 670, 467, 841, 401, 209, 596, 862, 702, 21, 219, 902, 271, 293, 350, 357, 182, 179, 909, 874, 769, 192, 39, 7, 487, 571, 155, 565, 231, 36, 544, 443, 24, 596, 570, 129, 585, 529, 557, 833, 270, 241, 732, 569, 839, 762, 881, 177, 149, 413, 806, 545, 591, 721, 289, 453, 53, 470, 215, 480, 218, 787, 915, 532, 626, 18, 349, 216, 338, 572, 979, 939, 76, 55, 49, 727, 524, 68, 403, 941, 234, 85, 991, 698, 561]

root = BSTree(arr[0])

for i in range(1,len(arr)):

    root.insert(arr[i],root.root)

level_order_tree=[]

levelOrderTraversal(root.root)

print(temp)

Same code in picture format to understand the indentation -

The output will be -

Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
Duplicate value!
[199, 120, 666, 97, 134, 411, 930, 18, 116, 125, 160, 379, 534, 751, 983, 6, 71, 106, 132, 154, 170, 312, 405, 437, 575, 716, 908, 931, 990, 1, 17, 40, 73, 114, 129, 151, 155, 195, 228, 324, 382, 421,
488, 544, 622, 675, 740, 904, 909, 966, 985, 995, 4, 7, 39, 55, 84, 149, 173, 198, 214, 310, 314, 377, 381, 386, 419, 431, 459, 529, 539, 553, 594, 654, 671, 681, 719, 748, 835, 926, 937, 981, 991, 27, 43, 69, 76, 92, 172, 182, 207, 217, 304, 327, 378, 384, 404, 415, 428, 450, 462, 500, 530, 545, 558, 587, 601, 651, 670, 710, 718, 736, 743, 768, 842, 923, 953, 974, 25, 36, 52, 68, 90, 179, 192, 203, 211, 215, 219, 297, 308, 328, 401, 413, 427, 447, 453, 464, 506, 532, 546, 557, 568, 583, 591, 596, 603, 636, 652, 695, 714, 729, 760, 821, 837, 857, 921, 948, 961, 979, 23, 49, 53, 85, 177, 209, 216, 218, 278, 346, 403, 426, 441, 487, 501, 524, 549, 560, 572, 577, 585, 614, 627, 638, 691, 702, 721, 732, 753, 762, 807, 831, 841, 856, 884, 915, 939, 962, 19, 24, 258, 281, 338, 352, 443, 486, 548, 565, 571, 626, 633, 683, 696, 727, 806, 833, 839, 851, 883, 900, 938, 941, 21, 249, 259, 279, 293, 350, 369, 470, 561, 570, 630, 698, 805, 880, 891, 902, 244, 271, 289, 349, 357, 467, 480, 569, 793, 870, 881, 893, 239, 270, 776, 796, 863, 874, 896, 231, 241, 769, 780, 862, 234, 789, 787]

So the original array had 300 elements but in BST we have 265 elements

For in enumeration an unbalanced Tree we have number of formations possible -

T(n) = (2n)! / (n+1)!n!

Number of Labeled Tees = (Number of unlabeled trees) * n!
                       = [(2n)! / (n+1)!n!]  × n!

n=265 Therefore finally we get,

Number of Labeled Tees = (Number of unlabeled trees) * 265! = [(530)! / (267)!265!] × 265!