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

class bst:
    def __init__(self):
        self.head = None
        
    def insertNode(self, data):
        
        newnode = node(data)
        
        if self.head == None:
            self.head = newnode
        else:
            current = self.head
            
            while current is not None:
                if data > current.data:
                    current = current.right
                else:
                    current = current.left
            current = newnode
    

bst = bst()
bst.insertNode(5)
bst.insertNode(10)
bst.insertNode(2)
current = bst.head
print(current.data)
print(current.right)

I have written a code for the best where the head is always pointing to the root node and there is a while loop which is to find the path to insert the new element to the tree but it is not woking ?? why

CodePudding user response：

In this situation, it may be easier to understand and complete the problem using a recursive approach. We can use recursion to explore the tree, traversing all nodes. Try something like this:

def insert(root, data):
    if root is None:
        return Node(data)
    else:
        if root.data == data:
            return root
        elif root.data < data:
            root.right = insert(root.right, data)
        else:
            root.left = insert(root.left, data)
    return root

CodePudding user response：

In your while loop before assigning current to either the Left or Right Tree check whether the Left or Right Child is None, then add a stop condition (break) if the child is None and you have assigned the newnode to it as in the code below

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

class bst:
    def __init__(self):
        self.head = None
    
def insertNode(self, data):
    
    newnode = node(data)
    
    if self.head == None:
        self.head = newnode
    else:
        current = self.head
        
        while current is not None:
            if data > current.data:
                if current.right!=None:
                    current = current.right
                else:
                    current.right=newnode
                    break
            else:
                if current.left!=None:
                    current = current.left
                else:
                    current.left=newnode
                    break
        current = newnode


bst = bst()
bst.insertNode(5)
bst.insertNode(10)
bst.insertNode(2)
current = bst.head
print(current.data)
print(current.right)

CodePudding user response：

The problem is that you are separating the tree and the search into different classes, also, you initialize left and right as None and they will never be giving a value, so your loop will always end setting current as None. Here is an example of what you are trying to make.

class Tree(object):
    def __init__(self, entry, left=None, right=None):
        self.entry = entry
        self.left = left
        self.right = right
    
    def insert(self, item, tree):
        if (item < tree.entry):
            if (tree.left != None):
                self.insert(item, tree.left)
            else:
                tree.left = Tree(item)
        else:
            if (tree.right != None):
                self.insert(item, tree.right)
            else:
                tree.right = Tree(item)

As you can see I added a check for right and left in case they are None, in which case they are given the item's value.

CodePudding user response：

The problem lies in the current = newnode. You should not directly assign newnode to current, which will only rebind current to it.

def insert(self, data):
    current = self.head
    parent = None

    while current is not None:
        if data == current.data:
            return
        parent = current
        current = current.left if data < current.data else current.right

    newnode = node(data)
    if parent is None:
        self.head = newnode
    elif data < parent.data:
        parent.left = newnode
    else:
        parent.right = newnode

Your mistakes are similar to the following:

>>> lst = [None, None]
>>> current = lst[0]
>>> print(current)
None
>>> current = 1
>>> lst    # not change
[None, None]

current simply points to the first item in the list. If you re assign value, you will only make current point to other value, which will not modify the contents of the list.