Implementation of a Binary Search Tree in Python with BST Class and Node Class

Question

Can Anyone help me figure out What it the wrong thing I did so I get this output Error--> NameError: name 'root' is undefined.

When I test the program for the inserting of the first root of the tree the inserting function works correctly and the first root was created successfully but Once I assign root to current and the while loop to search for a parent then insert the new value on it, I come up with the NameError :/

Here is the implementation of my code using python:

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

class BST:
  def __init__(self):
      self.root = None
  
  def insert(self, value):
    if root is None:
      root == Node(value)
     
    current = root
    while(True):
      if(value < current.value):
        if current.left:
          current.left = Node(value)
          break
        current = current.left
      else:
        if current.right:
          current.right = Node(value)
          break
        current = current.right


if __name__ == '__main__':
  tree = BST()
  tree.insert(10)
  tree.insert(5)
  tree.insert(6)
  print("Tree Inserted Successfully")

Thank you

I am trying to insert a new value in my binary search tree, so there is 2 scenarios:

• if the BST is empty (this is simple and pass correctly)
• the other scenario is when we have to find the parent of this node and insert its value, for that i go with while(true) and assigning a new variable current to root to keep track of current parent while traversing the tree with loop

Answer 1

The issues:

• root should be self.root.

• == is not an assignment. It should be =

• you should exit the function after setting the root, and not continue with the rest of the function:

  if self.root is None:
    self.root = Node(value) # Assign!
    return  # don't continue
  

• The conditions in the if statements that you have in the while loop, should be testing the opposite. When you don't have a left child, then you should attach a new node there, not when there is already a node there:

    if(value < current.value):
      if not current.left:  #  Opposite condition
        current.left = Node(value)
        break
      current = current.left
    else:
      if not current.right:  #  Opposite condition
        current.right = Node(value)
        break
      current = current.right
  

All code:

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

class BST:
  def __init__(self):
      self.root = None
  
  def insert(self, value):
    if self.root is None:  # root is an attribute, not a variable
      self.root = Node(value)  # Assign!
      return # Don't continue
     
    current = self.root
    while(True):
      if(value < current.value):
        if not current.left:  #  Opposite condition
          current.left = Node(value)
          break
        current = current.left
      else:
        if not current.right:  #  Opposite condition
          current.right = Node(value)
          break
        current = current.right


if __name__ == '__main__':
  tree = BST()
  tree.insert(10)
  tree.insert(5)
  tree.insert(6)
  print("Tree Inserted Successfully")
  print(tree.root.left.right.value)  # Should output: 6