Binary search tree in Python

Question

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)

• Patrick Mevzek: 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.

Answer 1

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.

• Anshul Goyal: 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
• Anshul Goyal: Hence downvoted..
• hjpotter92: @mu無 ah, yes. I did not think of that. Fixing it now!

Answer 2

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)

Answer 3

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