2

I'm trying to implement a class instance of a Binary Search Tree, but I think there's something wrong with my insert function.

Node class:

class Node:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

BST class:

class BST:
  def __init__(self):
    self.root = None

  def insert(self, node):
    def helper(current, node):
      if current is None:
        current = node
      else:
        if node.data < current.data:
          helper(current.left, node)
        elif node.data > current.data:
          helper(current.right, node)

    return helper(self.root, node)

  def inorder(self, current):
    if current:
      self.inorder(current.left)
      print(current.data)
      self.inorder(current.right)

Functions I'm calling:

tree = BST()
tree.root = Node(3)
tree.insert(Node(2))
tree.insert(Node(7))
tree.insert(Node(9))
tree.insert(Node(7))
tree.insert(Node(4))
tree.insert(Node(89))
tree.insert(Node(6))
tree.insert(Node(2))
tree.inorder(tree.root)
aemach
  • 33
  • 2
  • To start, you shouldn't have to initialize `tree.root` explicitly. `tree.insert(Node(2))` should work on an empty tree. In fact, `root` should not be part of the public interface to your class at all. – chepner Sep 30 '19 at 18:10
  • I'd think that stepping through your code in a debugger, like PyCharm's, would be super helpful to understand what's going on. – Random Davis Sep 30 '19 at 18:11

1 Answers1

1

Assigning current = node doesn't edit any objects, it just reassigns the local variable current. You need to modify the nodes to add children. Try this:

def helper(current, node):
    if node.data < current.data:
            if (current.left is None):
                current.left = node
                return
            else:
                helper(current.left, node)
        elif node.data > current.data:
          if (current.right is None):
              current.right = node
              return
          else:
              helper(current.right, node)
Simon Crane
  • 2,122
  • 2
  • 10
  • 21
  • Huh. That works, thanks! If I'm just reassigning the local variable in my code, how come assigning current.left in your code is modifying the actual node and not just the local variable? Also - I'm a bit confused about how to pass around the nodes in a function. Does python create a copy of the node when you pass it into a function? – aemach Sep 30 '19 at 18:20
  • `current.left` is an instance variable that belongs to the node object `current`. When the variable `current` goes out of scope, the object still exists, and its instance variables still have their values. Objects in python are passed by reference, see https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value for more about what this means, but basically: No, it doesn't create a copy, it tells the function where to find the value. – Simon Crane Sep 30 '19 at 18:27
  • Okay I see. But if objects are passed by reference in Python, then how come ```current=node``` creates a new local variable called ```current``` instead of reassigning the originally passed in object? – aemach Sep 30 '19 at 20:38
  • @aemach The function receives a reference to a node. It calls that reference `current`. Later, `current=foo` moves the reference to point at something else instead of the function's argument. `current.left = foo` would follow the reference `current` to get the node object, then tells it reassign its reference called `left`. The function doesn't have a direct reference to `current.left` because such a thing might not exist depending on the type of `current`, so it has to retrieve the actual node object before finding a reference called `left` to reassign – Simon Crane Sep 30 '19 at 20:43