Homework 7

Due Date: Wednesday, October 25th at 11:59 PM

Problem 2: Binary Tree Class

A binary search tree is a binary tree with the invariant that for any particular node the left child is smaller and the right child is larger. Create the class BinaryTree with the following specifications:

__init__(self): Constructor takes no additional arguments

insert(self, val): This method will insert val into the tree

(Optional) remove(self, val): This will remove val from the tree.

If the node to be deleted has no children then just remove it.
If the node to be deleted has only one child, remove the node and replace it with its child.
If the node to be deleted has two children, replace the node to be deleted with the maximum value in the left subtree. Finally, delete the node with the maximum value in the left-subtree.

getValues(self. depth): Return a list of the entire row of nodes at the specified depth with None at the index if there is no value in the tree. The length of the list should therefore be $2^{\text{depth}}$.

Here is a sample output:

bt = BinaryTree()
arr = [20, 10, 17, 14, 3, 0]
for i in arr:
    bt.insert(i)

print("Height of binary tree is {}.\n".format(len(bt)))
for i in range(len(bt)):
    print("Level {0} values: {1}".format(i, bt.getValues(i)))

Height of binary tree is 4.

Level 0 values: [20]
Level 1 values: [10, None]
Level 2 values: [3, 17, None, None]
Level 3 values: [0, None, 14, None, None, None, None, None]

Note that you do not need to format your output in this way. Nor are you required to implement a __len__ method to compute the height of the tree. I did this because it was convenient for illustration purposes. This example is simply meant to show you some output at each level of the tree.



In [1]:

    
import numpy as np
class BinaryTree:
    def __init__(self):
        self.data = [None]
        
    def insert(self, val):
        # keep track of idx we're at traversing the tree
        idx = 0
        while self.data[idx] is not None:
            idx = idx * 2 + (1 if self.data[idx] > val else 2)
            if idx >= len(self.data):
                self.data = self.data + [None]*(idx + 1 - len(self.data))
        self.data[idx] = val
        
    def find(self, val):
        idx = 0
        while self.data[idx] is not None and self.data[idx] != val:
            idx = idx * 2 + (1 if self.data[idx] > val else 2)
            if len(self.data) <= idx:
                return -1
        return idx if self.data[idx] is not None else -1
    
    def levelUp(self, idx):
        self.data[idx] = None
        leftChild = idx * 2 + 1
        rightChild = (idx + 1) * 2
        if len(self.data) > leftChild:
            if self.data[leftChild] is not None:
                self.data[idx] = self.data[leftChild]
                self.levelUp(leftChild)
            elif len(self.data) > rightChild and self.data[rightChild] is not None:
                self.data[idx] = self.data[rightChild]
                self.levelUp(rightChild)
                
    def getValues(self, level):
        values = []
        for x in range(2**level - 1, 2**(level + 1) - 1):
            if len(self.data) <= x:
                values.append(None)
            else:
                values.append(self.data[x])
        return values