CODEWITHSUNDEEP
pythonrecursionbinary-search-tree
aemach
aemach

Reputation: 33

What is wrong with my current implementation of a binary search tree? Printing the tree at the end only prints the root

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)

Upvotes: 2

Views: 42

Answers (1)

Simon Crane
Simon Crane

Reputation: 2182

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)

Upvotes: 1

Related Questions