-
Notifications
You must be signed in to change notification settings - Fork 0
/
SearchGivenKeyInBSTRecursive.java
82 lines (71 loc) · 2.08 KB
/
SearchGivenKeyInBSTRecursive.java
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package Practice;
/**
* SearchGivenKeyInBSTRecursive
*/
public class SearchGivenKeyInBSTRecursive {
class Node{
int data;
Node left, right;
Node(int data){
this.data = data;
this.left = this.right = null;
}
}
Node insert(Node root, int val){
if(root == null){
return new Node(val);
}
if(root.data > val){
root.left = insert(root.left, val);
}
if(root.data < val){
root.right = insert(root.right, val);
}
return root;
}
void inorder(Node root){
if(root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
void search(Node root, int key, Node parent){
if(root == null){
System.out.println("Key not found");
return;
}
if(parent == null){
if(root.data == key){
System.out.println("Given Key "+ key + " is the root node of the BST");
return;
}
}
if(parent != null){
if(parent.left.data == key){
System.out.println("Given Key "+ key + " is the left child of node "+ parent.data );
return;
}else if(parent.right.data == key){
System.out.println("Given Key "+ key + " is the right child of node "+ parent.data );
return;
}
}
if(root.data > key){
search(root.left, key, root);
}else if(root.data < key){
search(root.right, key, root);
}
}
public static void main(String[] args) {
SearchGivenKeyInBSTRecursive x= new SearchGivenKeyInBSTRecursive();
Node root = null;
int[] keys = new int[]{ 15, 10, 20, 8, 12, 16, 25 };
for(int key:keys){
root = x.insert(root, key);
}
System.out.println("input inorder:" );
x.inorder(root);
System.out.println("\noutput:");
x.search(root, 100, null);
}
}