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

trincot · Accepted Answer · 2022-03-25 13:52:35Z

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

edited Mar 25, 2022 at 13:52

answered Mar 25, 2022 at 13:45

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Khadija Over a year ago

Thank you @trincot for your help. It has been a long time when I didn't use python, maybe I need to refresh my memory with python's syntax ;)

Khadija Over a year ago

Sir @trincot may I ask you. what is the difference between having insert in the Node class and another one in Binary_search_tree class? I couldn't comment in your post there b/c I have less than 50reputation, stackoverflow.com/questions/62406562/… that's why i write it here

trincot Over a year ago

Both are possible. When you would define an insert method in the Node class, you would still want to have a little method on the Binary_search_tree class too, which would call the one on the Node class. If you cannot figure it out, then you can always start a new question, providing the code and your question about it.

Khadija Over a year ago

I do, I figure out, it's kinda a helper function at BST class.. Actually, in that post I was looking for the representation of the binary tree and I didn't pay attention to what is inside the insert method of BST class. Thank you again for your help

Collectives™ on Stack Overflow

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

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related