2
\$\begingroup\$

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)
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 10 '18 at 20:09
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$ Apr 10 '18 at 15:42
  • \$\begingroup\$ Hence downvoted.. \$\endgroup\$ Apr 10 '18 at 15:47
  • \$\begingroup\$ @mu無 ah, yes. I did not think of that. Fixing it now! \$\endgroup\$
    – hjpotter92
    Apr 11 '18 at 1:56
3
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.