PROBLEM DESCRIPTION: https://practice.geeksforgeeks.org/problems/insert-a-node-in-a-bst/1#
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.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//User function Template for Java
// class Node
// {
// int data;
// Node left, right;
// public Node(int d)
// {
// data = d;
// left = right = null;
// }
// }
class Solution{
// The function returns the root of the BST (currently rooted at 'root')
// after inserting a new Node with value 'Key' into it.
Node insert(Node root, int Key)
{
//Create temporary node for traversal
Node current = root;
//While the current node is not null:
while(current != null){
//If the current node has the key, end
if(current.data == Key)
break;
//If not, check if the Key is less than the data in current node. Move to left if that's the case
else if(Key < current.data){
//If left Node of current is not null, go to left Node since we can find for Key on the left
if(current.left != null)
current = current.left;
//If left Node is null, since Key is less than the current node.data, we will need to add a Node to left
else
{
Node newNode = new Node(Key);
current.left = newNode;
break;
}
}
//Same logic but on the right part of the tree
else{
if(current.right != null)
current = current.right;
else{
Node newNode = new Node(Key);
current.right = newNode;
break;
}
}
}
//return root as per the question
return root;
}
}