Binary Search Tree insertion in Python not returning to console

while learning about BSTs in hackerrank, I came across the following issue.

My classes for the Node and for the Binary Search Tree is defined as follows:

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

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

def insert(self,val):
currentNode = self.root
if currentNode is None:
self.root = Node(val)
elif currentNode.info > val:
currentNode.left = insert(currentNode.left,val)
elif currentNode.info < val:
currentNode.right = insert(currentNode.right,val)
return currentNode


However, performing a traversal on tree = BinarySearchTree() after using tree.insert(arr[i] over a for loop for some array of integers arr returns no output. The logic seems correct to me, and I suspect that this is due to a difference in type between Node and BST, but I am unsure of how to resolve this.

tree = BinarySearchTree()

tree.insert(arr[i]

arr

Edit: below is the full code from hackerrank. The only bit I was able to edit is the insert function.

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

    def __str__(self):
        return str(self.info) 

def preOrder(root):
    if root == None:
        return
    print (root.info, end=" ")
    preOrder(root.left)
    preOrder(root.right)
    
class BinarySearchTree:
    def __init__(self): 
        self.root = None

def insert(self,val):
currentNode = self.root
if currentNode is None:
self.root = Node(val)
elif currentNode.info > val:
currentNode.left = insert(currentNode.left,val)
elif currentNode.info < val:
currentNode.right = insert(currentNode.right,val)
return currentNode

tree = BinarySearchTree()
t = int(input())

arr = list(map(int, input().split()))

for i in range(t):
    tree.insert(arr[i])

preOrder(tree.root)


The given test case was

6
4 2 3 1 7 6


and was supposed to return 4 2 3 1 7 6, but no output was returned.

4 2 3 1 7 6

Edit: made the changes according to the first answer! Now, I have the following week error:

Traceback (most recent call last):
File “solution.py”, line 40, in <module>
tree.insert(arr[i])
File “solution.py”, line 30, in insert
currentNode.left = insert(currentNode.left,val)
NameError: name ‘insert’ is not defined


3 Answers
3

change your code to

def insert(self, val, currentNode):

if self.root is None:
self.root = Node(val)

elif currentNode.info > val:
if currentNode.left is None
currentNode.left = Node(val)
else:
self.insert(val, currentNode.left)

elif currentNode.info < val:

if currentNode.right is None
currentNode.right = Node(val)
else:
self.insert(val, currentNode.right)


and call it via

tree.insert(val,tree.root)


self.function()

elif currentNode.info > val: currentNode.left = insert(currentNode.left,val)

currentNode = self.root

i think the problem lies here

def insert(self,val):
currentNode = self.root
if currentNode is None:
currentNode = Node(val)
elif currentNode.info > val:
currentNode.left = insert(currentNode.left,val)
elif currentNode.info < val:
currentNode.right = insert(currentNode.right,val)
return currentNode


as you can see you do "insert" the node but you dont assign it, the code block

if currentNode is None:
currentNode = Node(val)


should be

if currentNode is None:
self.root = Node(val)


you keep on trying to traverse a Null tree

EDIT: Its possible that this is not the problem, please provide the full code the create() function is missing from your code but is called

create()

Here's a somewhat shorter version which avoids nested "if" statements and without the "Node" class:

class BinarySearchTree:
def __init__(self):
self.info = None
self.left = None
self.right = None

def insert(self,val):
if self.info is None:
self.info = val
self.left = BinarySearchTree()
self.right = BinarySearchTree()
elif self.info > val:
self.left.insert(val)
elif self.info < val:
self.right.insert(val)


Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.