Create a Binary Tree

The following code is taken from the O'reilly data structures with Python tutorialon Binary trees
It is just used as an example of best practices which can be adapted similarly for the Random Intersection Tree/ Node classes we will create

List Recursion



In [1]:

    
# Step by Step version
def search(aList, target):
    for v in aList:
        if target == v:
            return True
    return False



In [2]:

    
# Recursive approach
def searchRecursive(aList, target):
    if len(aList) == 0:
        return False
    if aList[0] == target:
        return True
    return searchRecursive(aList[1:], target)



In [7]:

    
max_val   = 1000
newList   = range(max_val)
newTarget = max_val



In [8]:

    
%timeit search(aList = newList, target = max_val)









    



38.8 µs ± 810 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)



In [9]:

    
%timeit searchRecursive(aList = newList, target = max_val)









    



676 µs ± 5.69 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Comments

The recursive approach in this example is about 18 times slower than the iterative approach
There is a recursion limit issue, which is needs to be considered in recursive algorithms

Linked Node example



In [11]:

    
class LinkedNode:
    def __init__(self, value):
        self.value = value
        self.next  = None



In [12]:

    
def search(n, value):
    # Base case
    if n is None:
        return False
    
    # Action and recursive step
    if n.value == value:
        return True
    return search(n.next, value)



In [13]:

    
def sumList(n):
    # base case
    if n is None:
        return 0
    
    # Action and recursive step
    return n.value + sumList(n.next)



In [14]:

    
class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left  = None
        self.value = None
    
class BinaryTree:
    def __init__(self):
        self.root = None

Implement the Binary Tree



In [49]:

    
class BinaryNode:
    # Don't initially know what the left and right nodes
    # are
    def __init__(self, value):
        self.value = value
        self.left  = None
        self.right = None
        
    def add(self, value):
        if value <= self.value:
            # add to left
            self.left = self.addToSubTree(self.left, value)
        elif value > self.value:
            # add to right
            self.right = self.addToSubTree(self.right, value)
    
    def addToSubTree(self, parent, value):
        if parent is None:
            return BinaryNode(value)
        parent.add(value)
        return parent
    
    def remove(self, value):
        if value < self.value:
            self.left = self.removeFromParent(self.left, value)
        elif value > self.value:
            self.right = self.removeFromParent(self.right, value)
        else:
            # what if left subtree is empty
            if self.left is None:
                    return self.right
            # find the largest value in the left subtree
            child = self.left
            while child.right:
                child = child.right
            # find the largest value in the left subtree
            childKey = child.value
            self.left = self.removeFromParent(self.left, childKey)
            self.value = childKey
            
        return self
    
    def removeFromParent(self, parent, value):
        if parent:
            return parent.remove(value)
        return None

class BinaryTree:    
    def __init__(self):
        self.root = None
        
    # add value to BT
    def add(self, value):
        if self.root == None:
            self.root = BinaryNode(value)
        else:
            self.root.add(value)
    
    # remove value from BT
    def remove(self, value):
        if self.root is not None:
            self.root = BinaryNode(value)
        else:
            self.root.add(value)
    
    def __contains__(self, target):
        node = self.root
        while node is not None:
            if target < node.value:
                node = node.left
            elif target > node.value:
                node = node.right
            else:
                return True       
        return False



In [41]:

    
b = BinaryTree()
b.root



In [42]:

    
b.add(7)



In [43]:

    
b.root









    Out[43]:





<__main__.BinaryNode at 0x111f32208>



In [44]:

    
b.root.value









    Out[44]:





7



In [45]:

    
b.add(1)



In [46]:

    
b.root.value









    Out[46]:





7



In [47]:

    
b.root.right



In [48]:

    
1 in b









    Out[48]:





True



In [50]:

    
b = BinaryTree()



In [51]:

    
b.add(1)



In [53]:

    
b.root.value









    Out[53]:





1



In [54]:

    
1 in b









    Out[54]:





True



In [58]:

    
b.remove(1)



In [59]:

    
b









    Out[59]:





<__main__.BinaryTree at 0x111e66b38>



In [60]:

    
1 in b









    Out[60]:





True



In [ ]: