Given a BST and a key K. If K is not present in the BST, Insert a new Node with a value equal to K into the BST. 
Note: If K is already present in the BST, don't modify the BST.
Example 1:
Input:
     2
   /   \
  1     3
K = 4
Output: 1 2 3 4
Explanation: After inserting the node 4
Inorder traversal will be 1 2 3 4.
Example 2:
Input:
        2
      /   \
     1     3
             \
              6
K = 4
Output: 1 2 3 4 6
Explanation: After inserting the node 4
Inorder traversal of the above tree
will be 1 2 3 4 6.
Your Task:
You don't need to read input or print anything. Your task is to complete the function insert() which takes the root of the BST and Key K as input parameters and returns the root of the modified BST after inserting K. 
Note: The generated output contains the inorder traversal of the modified tree.
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 <= Number of nodes initially in BST <= 10^{5}
1 <= K <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: #User function Template for python3





#Function to insert a node in a BST. 

def insert(root, Key):

    # code here

Solutions:
def insert(root, Key):
	if root == None:
		return Node(Key)
	elif root.data == Key:
		return root
	elif root.data > Key:
		root.left = insert(root.left, Key)
	else:
		root.right = insert(root.right, Key)
	return root


def insert(root, Key):
	if root is None:
		return Node(Key)
	parent = None
	curr = root
	while curr != None:
		parent = curr
		if curr.data == Key:
			return root
		if Key < curr.data:
			curr = curr.left
		else:
			curr = curr.right
	if Key < parent.data:
		parent.left = Node(Key)
	else:
		parent.right = Node(Key)
	return root


def insert(root, Key):
	if root == None:
		root = Node(Key)
	if Key > root.data:
		root.right = insert(root.right, Key)
	if Key < root.data:
		root.left = insert(root.left, Key)
	return root


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


class Node:

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

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


def insert(root, val):
	if root == None:
		return Node(val)
	cur = root
	while True:
		if cur.data == val:
			break
		if cur.data < val:
			if cur.right:
				cur = cur.right
			else:
				cur.right = Node(val)
				break
		elif cur.left:
			cur = cur.left
		else:
			cur.left = Node(val)
			break
	return root


def insert(root, Key):
	if not root:
		root = Node(Key)
	while root:
		if root.data == Key:
			return
		elif root.data > Key:
			if root.left:
				root = root.left
				continue
			root.left = Node(Key)
			break
		else:
			if root.right:
				root = root.right
				continue
			root.right = Node(Key)
			break


def insert(root, Key):
	curr = root
	while curr:
		changeNode = curr
		if curr.data == Key:
			return root
		elif curr.data > Key:
			curr = curr.left
		else:
			curr = curr.right
	if changeNode is None:
		return Node(Key)
	if changeNode.data > Key:
		changeNode.left = Node(Key)
	else:
		changeNode.right = Node(Key)
	return root


def insert(root, key):
	prev = None
	temp = root
	while temp != None:
		if key == temp.data:
			return
		elif key > temp.data:
			prev = temp
			temp = temp.right
		else:
			prev = temp
			temp = temp.left
	if key > prev.data:
		prev.right = Node(key)
	else:
		prev.left = Node(key)


def insert(root, Key):
	curr = root
	prev = None
	while curr is not None:
		if curr.data == Key:
			return root
		prev = curr
		if curr.data < Key:
			curr = curr.right
		else:
			curr = curr.left
	node = Node(Key)
	if prev is None:
		return node
	if Key < prev.data:
		prev.left = node
	else:
		prev.right = node
	return root


def insert(root, key):
	if root == None:
		newNode = Node(key)
		return newNode
	if root.data == key:
		return root
	if root.data > key:
		root.left = insert(root.left, key)
	else:
		root.right = insert(root.right, key)
	return root


def insert(root, Key):
	n = Node(Key)
	if root == None:
		return n
	curr = root
	while curr != None:
		if curr.data == Key:
			return root
		if curr.data < Key:
			if curr.right == None:
				curr.right = n
				return root
			curr = curr.right
		else:
			if curr.left == None:
				curr.left = n
				return root
			curr = curr.left


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


class Node:

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

def insert(root, key):
	temp = root
	a = Node(key)
	if temp is None:
		root = a
	else:
		pre = temp
		while temp:
			pre = temp
			if temp.data > key:
				temp = temp.left
			elif temp.data == key:
				return root
			else:
				temp = temp.right
		if pre.data > key:
			pre.left = a
		else:
			pre.right = a
	return root


def insert(root, key):
	bst(root, key)
	return

def bst(root, key):
	if root.data == key:
		return
	if root.data > key:
		if root.left:
			bst(root.left, key)
		else:
			root.left = Node(key)
			return
	if root.data < key:
		if root.right:
			bst(root.right, key)
		else:
			root.right = Node(key)
			return


def insert(root, Key):

	def ins(roo):
		if not roo:
			return Node(Key)
		elif roo.data < Key:
			roo.right = ins(roo.right)
		elif roo.data > Key:
			roo.left = ins(roo.left)
		return roo
	return ins(root)


def insert(root, Key):
	if root == None:
		return Node(Key)

	def ins(root, key):
		if root.data == key:
			return
		if root.data < Key:
			if root.right == None:
				root.right = Node(Key)
			ins(root.right, key)
		else:
			if root.left == None:
				root.left = Node(Key)
			ins(root.left, key)
	ins(root, Key)
	return root


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


def insert(root, Key):

	def dfs(n):
		if n.data == Key:
			return
		if n.data < Key:
			if not n.right:
				n.right = Node(Key)
			else:
				dfs(n.right)
		if n.data > Key:
			if not n.left:
				n.left = Node(Key)
			else:
				dfs(n.left)
	dfs(root)


class Node:

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

def insert(root, Key):
	if root == None:
		root = Node(Key)
		return root
	if Key > root.data:
		root.right = insert(root.right, Key)
	if Key < root.data:
		root.left = insert(root.left, Key)
	return root


def has(root, key):
	while root:
		if root.data == key:
			return True
		if root is not None and root.data < key:
			root = root.right
		elif root is not None and root.data > key:
			root = root.left
	return False

def insert(root, Key):
	if root is None:
		return Key
	if has(root, Key):
		return root
	qw = root
	while True:
		if qw is not None and qw.data < Key:
			if qw.right == None:
				qw.right = Node(Key)
				break
			qw = qw.right
		elif qw is not None and qw.data > Key:
			if qw.left == None:
				qw.left = Node(Key)
				break
			qw = qw.left
	return root


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


def insert(root, key):
	while root:
		if root.data == key:
			break
		if key < root.data:
			if not root.left:
				root.left = Node(key)
				break
			root = root.left
		else:
			if not root.right:
				root.right = Node(key)
				break
			root = root.right


def insert(root, Key):
	while root:
		if root.data == Key:
			break
		if Key < root.data:
			if root.left:
				root = root.left
			else:
				root.left = Node(Key)
				break
		elif root.right:
			root = root.right
		else:
			root.right = Node(Key)
			break


def insert(root, Key):
	if not root:
		return Node(Key)
	if root.data == Key:
		return root
	if Key < root.data:
		root.left = insert(root.left, Key)
	if Key > root.data:
		root.right = insert(root.right, Key)
	return root


def insert(root, key):
	new_node = Node(key)
	if root is None:
		return new_node
	curr = root
	parent = None
	while curr is not None:
		parent = curr
		if key < curr.data:
			curr = curr.left
		elif key > curr.data:
			curr = curr.right
		else:
			return root
	if key < parent.data:
		parent.left = new_node
	else:
		parent.right = new_node
	return root


def insert(root, Key):
	parent = None
	current = root
	while current != None:
		parent = current
		if current.data == Key:
			return root
		elif current.data > Key:
			current = current.left
		else:
			current = current.right
	if parent == None:
		return Node(Key)
	elif parent.data > Key:
		parent.left = Node(Key)
	else:
		parent.right = Node(Key)
	return root


def insert(root, Key):
	l = []
	key = Key

	def fun(root):
		if root:
			l.append(root.data)
			fun(root.left)
			fun(root.right)
	fun(root)
	if key in l:
		return root

	def fu(root, key):
		if root == None:
			y = Node(key)
			return y
		elif key > root.data:
			root.right = fu(root.right, key)
		elif key < root.data:
			root.left = fu(root.left, key)
		return root
	fu(root, key)
	return root


def insert(root, key):
	if root == None:
		root = Node(key)
		return
	cur = root
	while key != cur.data:
		if key < cur.data:
			if cur.left:
				cur = cur.left
			else:
				cur.left = Node(key)
				break
		elif cur.right:
			cur = cur.right
		else:
			cur.right = Node(key)
			break


def insert(root, key):
	parent = None
	curr = root
	while curr != None:
		parent = curr
		if curr.data == key:
			return root
		elif curr.data < key:
			curr = curr.right
		else:
			curr = curr.left
	if parent == None:
		return Node(key)
	if parent.data > key:
		parent.left = Node(key)
	else:
		parent.right = Node(key)
	return root


def insert(root, Key):
	temp = root

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


def insert(root, Key):
	current = root
	newnode = Node(Key)
	while current != None:
		if current.data == Key:
			break
		elif current.data > Key:
			if current.left == None:
				current.left = newnode
				break
			else:
				current = current.left
		elif current.right == None:
			current.right = newnode
			break
		else:
			current = current.right
	return root