# Binary search tree in Python

Create a binary search tree representation of a given array of integers.

How can I improve this code?

# Creating Node object class
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

# Creating Tree class
class BST(object):
def __init__(self, val):
self.root = Node(val)

def insert(self, value):
current = self.root
while current:
if value < current.value:
if current.left == None:
current.left = Node(value)
break
else:
current = current.left
else:
if current.right == None:
current.right = Node(value)
break
else:
current = current.right

# inputs
t = BST(22)
t.insert(30)
t.insert(10)
t.insert(80)
t.insert(90)
t.insert(9)
t.insert(23)
t.insert(14)
t.insert(6)
t.insert(40)
t.insert(60)
t.insert(3)

• Improve in what way and sacrifying what for it? Each choice is a compromise. Are you seeking to use less CPU? less memory? less number of lines? reducing McCabe complexity? etc. Apr 10 '18 at 20:09

For checking whether something is None, use the is and is not operators in place of ==.

You also do not need the break statements as the whole code is short circuited by if-else blocks. doesn't help because of a logical error

Rewritten:

class BST(object):
def __init__(self, val):
self.root = Node(val)

def insert(self, value):
current = self.root
while current:
if value < current.value:
if current.left is None:
current.left = Node(value)
break
else:
current = current.left
else:
if current.right is None:
current.right = Node(value)
break
else:
current = current.right


At the end, you should use the if __name__ guard for setting up the inputs/test section.

The rest all looks good.

• This code is logically incorrect.. if you don't break out of the while loop after assigning current.left or current.right, it will execute forever.. Since in the next iteration, current will still have a value, so while current will evaluate True, and this time, it goes in the inner else block where current becomes the newly assigned node.. and so on Apr 10 '18 at 15:42
• Hence downvoted.. Apr 10 '18 at 15:47
• @mu無 ah, yes. I did not think of that. Fixing it now! Apr 11 '18 at 1:56

You can also consider a very elegant, recursive solution:

def insert(self, value, node=self.root):
if node == null:
return Node(value)
if value < node.value:
node.left = self.insert(value, node.left)
else
node.right = self.insert(value, node.right)


Although, please mind that in case of large trees, efficiency of that solution is slightly lower (because of call stack)

There's some repetition, that @zlenyk exposed in his recursive answer that you can still use in your iterative answer:

def insert(self, value):
current = self.root

while current:
if value < current.value:
side = 'left'
else:
side = 'right'
next = getattr(current, side, None)
if next is None:
setattr(current, side, Node(value))
current = next


though it may be clearer as:

def insert(self, value):
current = self.root

def traverse(current, direction):
next = getattr(current, side, None)
if next is None:
setattr(current, side, Node(value))
return next

while current:
if value < current.value:
traverse(current, 'left')
else:
traverse(current, 'right')


or maybe that last bit should be:

    while current:
side = { True: 'left', False: 'right' }[value < current.value]
traverse(current, side)


...or maybe not. Your call, of course. It depends on if you want to optimize for speed, maintenance, or cleverness ;)