Binary search tree using and check if a given tree is binary serach tree Python

”’

Created on Aug 11, 2015

@author: ishaansutaria

”’

class Node():

    ”’

    Initialize a node with the data

    with both their childreen being null

    ”’

    def __init__(self,data):

        self.data = data

        self.left = None

        self.right = None

        

    

    ”’

    Using recursion

    1) If root is less/greater than data and null insert right/left.(return)

    2) Else if right/left node is not null call the function again with right/left node as root

    ”’

    def insertData(self,data):

        if self.data < data:

            if self.right == None:

                self.right = Node(data)

            else:

                self.right.insertData(data)

        elif self.data > data:

            if self.left == None:

                self.left = Node(data)

            else:

                self.left.insertData(data)

    

    

    ”’

    You need to traverse the list(in-order)

    Go to the leftmost node in the tree and print it

    Check if the node has right node and get to the leftmost node of that node

    and print the list.

    

    1) Check if root has a left child

    2) If yes call the function with the left child as the root node.

    3) print the root value

    4) Check if the root has right child

    5) If yes then call the function with the right child as the root    

    ”’

    def printBinaryList(self):

        if self.left != None:

            self.left.printBinaryList()

        print self.data

        if self.right != None:

            self.right.printBinaryList()

    

    

    

    ”’

    Recursion:

    1) Check if the root node matches the value is yes then return

    2) Else check if data to be found is less/greater than the root node.

    3) If yes/no call the function again with the left/right child as the root node.

    ”’

    def serachBinaryTree(self,data):

        if self.data == data:

            print ‘found’

            return data

        if self.data > data:

            if self.left != None:

                return self.left.serachBinaryTree(data)

        if self.data < data:

            if self.right != None:

                return self.right.serachBinaryTree(data)

    

    

    ”’

    Helper function for deleting a node

    Returns the number of childs a node has

    ”’

    def countChildreen(self):

        count = 0

        if self.left:

            count +=1

        if self.right:

            count +=1

        

        return count

    

    

    ”’

    

    ”’

    def delNode(self,data,parent=None):

        if self.data == data:

            if parent.data > data:

                self.right = self.left

                parent.left = self.right

            print ‘found’

            return data

        if self.data > data:

            if self.left != None:

                return self.left.serachBinaryTree(data,self)

        if self.data < data:

            if self.right != None:

                return self.right.serachBinaryTree(data,self)

        

    

    ”’

    Traverse a node in-order and append the values you print in an array.

    Check if the array and its sorted version are the same.

    (Here you can also use compare with the prev node removing the need to have an

    extra array)

    ”’ 

    def checkBinaryTree(self):

        

        temp = []

        stack = []

        while True:

            while self != None:

                temp.append(self)

                self = self.left

            if len(temp) == 0:

                break

            self = temp.pop()

            stack.append(self.data)

            while self.right != None and len(temp) != 0:

                self = temp.pop()

                #print  self.data

                stack.append(self.data)

            self = self.right

            break

        if sorted(stack) == stack:

            print ‘Binary tree’

        else:

            print ‘Not a binary tree’

    

            

            

        

            

root = Node(5)

root.insertData(8)

root.insertData(9)

root.insertData(6)

root.insertData(5)

#root.printBinaryList()

root.checkBinaryTree()

print root.serachBinaryTree(8)

            

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s