BinTree and BST

# A binary search tree example
# Ref. Internet, StackOverflow forum

# Extensively edited by G. Fleischer, 8/8/13, 3/15/14, 3/22/14

# This class is still incomplete as of 3/22/14: it lacks
##  an erase_tree method.

##************************************
## eraseTree method implemented 4/18/16

SPACE = " "*3

from random import randint # for testing purposes

class Node:
    """ Attributes: left , right, data  """
    ##left , right, data = None, None, 0

    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def isLeaf(self):
        return self.left is None and self.right is None

class BinTree:
    """Binary Tree"""

    def __init__(self, root = None):
        """ Creates empty tree """

        self.root = root
        self.size = 1 if root else 0



    def addNode(self, data):
            # creates a new treenode linked (rt or lf) to self
            self.size += 1
            return Node(data)

    def printRevTree(self, root, dep):
        """Prettyprints the contents of subtree rooted at node "root" in reverse inorder"""

        if root and self.size: #only print nonempty tree. Note lazy evaluation

            self.printRevTree(root.right,dep+1) #dep param.added by G.F.8/8/13
            if root.data is not None: # may not be necessary in the end
                print( SPACE * dep,root.data)
            self.printRevTree(root.left,dep+1)


    # ***************************
    # Trying erase
    # Algorithm: delete each leaf in Postorder

    def eraseTree(self, root): # Added 4/18/16 by G.F.
        if root:
            if root.isLeaf():
                print("Deleting",root.data)
                root = None
            else:
                self.eraseTree(root.left)
                self.eraseTree(root.right)
                print("Deleting",root.data)
                root = None


class BST(BinTree):
    """ Binary Search Tree"""


    def insert(self, root, data):

            # inserts a new data value in the correct location in the search tree
            # No duplication allowed

            if root is None: #We have just passed a leaf node, or started in
                    ## an empty tree
                    # if tree is empty, creates root node with the
                    # data value, otherwise hangs new node in the correct
                    # direction (R/L)  from the last leaf

                return self.addNode(data)
            else:
                # Insert into nonempty tree
                if data < root.data:
                # insert into the left sub-tree
                    root.left = self.insert(root.left, data)
                elif data > root.data:
                # insert into the right sub-tree
                    root.right = self.insert(root.right, data)
                # else value already in tree, ignored

                return root

    def lookup(self, root, target, schDep = [0]):

        """ Returns True iff target value found, and side-effects a search-depth global"""

        ## schDep is a list of one element, to make it a reference var
        # looks for a value into the tree
        # Side effect on global var. searchDepth!

        schDep[0] += 1

        if root is None: # leaf reached without a find, or tree is empty
            return False
        else:
                # if it has found it...
            if target == root.data:
                return True
            else:
                if target < root.data:
                        # continue searching in left subTree
                    return self.lookup(root.left, target,schDep)
                else:
                        # continue searching in right subtree
                    return self.lookup(root.right, target,schDep)

    def findMin(self, node):
            # goes down into the left
            # subtree of given node and returns the last value
        while(node.left):
            node = node.left
        return node.data

    def height(self, root):
        """ Define height of tree as -1 for empty tree,
0 for single node tree, and the larger of the heights of LST and RST
"""
        if root is None:
            return -1
        else:
            lheight = self.height(root.left)
            rheight = self.height(root.right)
            return 1 + max(lheight, rheight)

    def _size(self, root):
        """ Returns total number of nodes in the tree."""  #Built in redundancy
        if root is None:
            return 0
        else:
            return self._size(root.left) + 1 + self._size(root.right)

    def locate(self, root, target):
        """Partially duplicates the work of lookup, but returns two pointers
prev and current. Current is the node with data = target, prev its parent node """
        ## this method is only called if we know that target is in the tree

        prev = root
        current = root
        while current.data != target:
            prev = current
            if target < current.data:
                current = current.left
                prev.left = current
            else: # target  > current.data
                current = current.right
                prev.right = current
        return prev, current # Tuple (ordered pair) is returned

    def delete(self, root, target):
        """Deletes the node with data value == target
(while preserving the BST structure) """

        ## if target value not in tree, report and stop

        if self.size == 0:
            print("Attempting to delete from empty tree")
            return # No result

        if not self.lookup(root, target):
            print("Tree has no node with data value", target)
            return root


        self.size -= 1
        prev, current = self.locate(root, target)
        ## Post-Condition: current.data == target
        #DEBUG
        print(prev.data, current.data)

        if current.isLeaf():
            if prev.left is current: prev.left = None
            else: prev.right = None
            current = None

            return root # We are done

        # otherwise current has at most one child.

        # Case of exactly one child
        if current.left is None: # there is a right child only
            if prev.right is current: #current is right child of prev
                prev.right = current.right
                current.right = None
                current = None
            elif prev.left is current:
                prev.left = current.right
                current.right = None
                current = None

            elif prev is current: ## target is at the root of the tree
                assert current is root
                if current is not root: raise AssertionError ("current should equal the root")

                # DEBUG
                print("Deleting  root with right branch only")

                current = root.right
                root.right = None
                root = current
                prev = current = None

            return root # We are done

        elif current.right is None: # there is a left child only
            if prev.right is current: #current is right child of prev
                prev.right = current.left
                current.left = None
                current = None
            elif prev.left is current: # current is left child of prev
                prev.left = current.left
                current.left = None
                current = None



            elif prev is current: ## target is at the root of the tree
                assert current is root
                if current is not root: raise AssertionError ("current should equal the root")

                # DEBUG
                print("Deleting  root with left branch only")

                current = root.left
                root.left = None
                root = current
                prev = current = None


            return root # We are done

        ## End case of exactly one child of current

        else: # current has two children
            ## Find the leftmost descendant of current's right child
            # = the logical successor of current in inOrder

            ## Strategy: the Pipeline Technique

            temp = current.right
            temp_prev = temp

            if temp.left is None: ## Right child IS the logical successor
                current.right = temp.right

            else:
                ## Find leftmost child of temp
##                while temp.left is not None:
                while temp.left:
                    temp_prev = temp
                    temp = temp.left
                # Leftmost descendant of right child is now located.

                temp_prev.left = temp.right # works even if temp is a leaf

            ## Ready for the key step
            # Overwrite target with data field of leftmost descendant
            # of right child.
            current.data = temp.data

            # Now unconditionally remove all temporary references
            temp.right = None
            temp.left = None #superfluous?
            temp = None

            prev = current = None

            return root




    def printTree(self, root):
        ##Inorder traversal [G.F.]

        if root is not None:
            self.printTree(root.left)
            print( root.data, end = ' ')
            self.printTree(root.right)





###                     ******* Test runs *******
print("Type go(<int>) to start")
def go(numNodes = 0):

    if __name__ == "__main__":
        # create the binary tree
        if numNodes == 0:
            print("Empty tree")
            return

        DEPTH = 1 #Used in prettyprinting. G.F. 8/8/13
        searchDepth = [0] # value side-effected by search function

        testData = []

        while len(testData) < numNodes:
            n =  randint(1,3 * numNodes)
            if n not in testData:
                testData.append(n)

        print("Data came in the following random order:")
        print(testData)

##        bTree = BST()
##        # add the root node
##        theRoot = bTree.addNode(testData[0])

        theRoot = Node(testData[0])
        bTree = BST( theRoot )

        # Enter the random data into the tree, or ask the user to insert values
        for i in range(1, numNodes):
            #data = int(input("insert the node value nr %d: " % i))

            data = testData[i]
            # insert values
            bTree.insert(theRoot, data)
        print("\n\tTree contents in sorted order :\n\t",end=' ')
        bTree.printTree(theRoot); print()

        print("Tree, prettyprinted:\n\t")
        bTree.printRevTree(theRoot,DEPTH)

        data = int(input("Value to find: ") )
        if bTree.lookup(theRoot, data, searchDepth):
            print( data, "found in %d trials" % (searchDepth[0]) )
        else:
            print(data, "not found")

        print("Minimum value stored :", bTree.findMin(theRoot))
        print("Height of tree: ", bTree.height(theRoot))
        print("Size of tree :", bTree.size)

        print("\nInserting more nodes, then print")

        while True:
            num = int(input("Type a value to insert, 0 to stop: "))
            if num == 0 : break
            else:
                bTree.insert(theRoot, num)
                bTree.printRevTree(theRoot,DEPTH)

        while bTree.size > 0:
            num = int(input("\nType a value to delete, 0 to stop: "))
            if num == 0 : break
            else:
                theRoot = bTree.delete(theRoot, num)
                print("Current size of tree:",bTree.size)
                bTree.printRevTree(theRoot,DEPTH)
        if bTree:
            yes_no = input("The tree is still not empty. Erase?")
            if yes_no[0].upper() == 'Y':
                bTree.eraseTree(theRoot)



##        bTree.erase(theRoot)
##        bTree.printRevTree(theRoot,DEPTH)
##