-
Notifications
You must be signed in to change notification settings - Fork 1k
/
RetrieveBTS.java
157 lines (140 loc) · 3.84 KB
/
RetrieveBTS.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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/*
Retrieve Binary Search Tree
You are provided with the roots of the binary search tree
where it has been conditionaaly mentioned that
any two of the nodes of the tree are swapped by mistake.
Your task is to recover the original tree without
changing any any of its configuration.
You have been asked to find a solution without the use of
extra space i.e. constant space.
*/
import java.io.*;
import java.util.Scanner;
import java.util.*;
//defining a class for storing nodes of tree
class BTNode
{
int value;
BTNode left;
BTNode right;
BTNode()
{}
BTNode(int value)
{
this.value = value;
}
BTNode(int value, BTNode left, BTNode right)
{
this.value = value;
this.left = left;
this.right = right;
}
}
public class RetrieveBST
{
//function of to recover the changed binary
//search tree
public void retrieveTree(BTNode root){
if(root == null)
{
return;
}
BTNode previous = null;
BTNode first = null, second = null;
while(root != null)
{
//for no node present at the left side of the tree
if(root.left == null)
{
//we print root
if(previous != null && previous.value > root.value)
{
if(first == null)
{
first = previous;
}
second = root;
}
previous = root;
root = root.right;
}
else
{
BTNode temp = root.left;
while(temp.right != null && temp.right != root)
{
temp = temp.right;
}
if(temp.right == null)
{
//then we move to extreme left
temp.right = root;
//moving to left
root = root.left;
}
else
{
temp.right = null;
//we print root
if(previous != null && previous.value > root.value)
{
if(first == null)
{
first = previous;
}
second = root;
}
previous = root;
root = root.right;
}
}
}
int temp = first.value;
first.value = second.value;
second.value = temp;
}
void printNode(BTNode node)
{
if(node == null)
{
return;
}
printNode(node.left);
System.out.print(" "+node.value);
printNode(node.right);
}
//driver code
public static void main (String[] args) throws IOException
{
// Taking input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the values of nodes for tree : ");
String str = br.readLine();
Node root = buildTree(str);
//for output
if(str.length() == 0 || str.charAt(0) == 'N')
{
return(System.out.println("Null"));
}
String ip[] = str.split(" ");
// Here we start creating the root of the tree
BTNode root = new BTNode(Integer.parseInt(ip[0]));
retrieveTree(root);
System.out.println("Retrieved tree is : ");
printNode(root);
}
}
/*
EXAMPLE:--
INPUT--
Enter the values of nodes for tree : 1 3 N N 2
OUTPUT--
Retrieved tree is : 3 1 N N 2
1 3
/ /
3 --> 1
\ \
2 2
TIME COMPLEXITY -- > O(N), where N is the number of nodes
SPACE COMPLEXITY -- > O(1)
*/