Write a function that takes in a root, value as arguments and returns the root with the new node inserted into the correct position of the binary search tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert_helper(root: Node, new_value: int):
if root.data < new_value:
# Go right
if root.right:
# Recursively call the right subtree
insert_helper(root.right, new_value)
else:
# Node to the right is empty, hence we can insert
root.right = Node(new_value)
else:
# Go left
if root.left:
insert_helper(root.left, new_value)
else:
# Node to the left is empty, hence we can insert
root.left = Node(new_value)