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\$ Commented Apr 10, 2018 at 20:09

3 Answers 3

Reset to default
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\$ Commented Apr 10, 2018 at 15:42
  • \$\begingroup\$ Hence downvoted.. \$\endgroup\$ Commented Apr 10, 2018 at 15:47
  • \$\begingroup\$ @mu無 ah, yes. I did not think of that. Fixing it now! \$\endgroup\$ Commented Apr 11, 2018 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\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.