# 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)