-
Notifications
You must be signed in to change notification settings - Fork 1
/
InOrderSuccessor.java
85 lines (70 loc) · 2.21 KB
/
InOrderSuccessor.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
package com.abn.dsalgos.challenges.BST;
import com.abn.dsalgos.utils.MyBSTNode;
/*
Find InOrder successor of a node in binary search tree
HINT : What is Inorder Successor: Inorder successor of a node is the next node in
the inorder traversal of the tree. For the last node in a tree,
inorder successor will be NULL
Case 1: If right subtree of node is not NULL, then successor is the left most child in right subtree
Case 2: If right subtree of node is NULL, then succ is one of the ancestors
*/
public class InOrderSuccessor<T extends Comparable<T>> {
MyBSTNode<T> root;
public InOrderSuccessor() {
root = null;
}
public void insertNode(MyBSTNode<T> node) {
if (root == null) {
root = node;
return;
}
MyBSTNode<T> current = root;
MyBSTNode<T> parent;
while (current != null) {
parent = current;
if (node.data.compareTo(current.data) < 0) {
current = current.left;
if (current == null) {
parent.left = node;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = node;
return;
}
}
}
}
public MyBSTNode<T> getSuccessor(MyBSTNode<T> root, MyBSTNode<T> node) {
MyBSTNode<T> successor = node.right;
MyBSTNode<T> current = root;
/*
Case 1:
*/
if (successor != null) {
while (successor.left != null) {
successor = successor.left;
}
return successor;
}
/*
Case 2:
*/
else {
MyBSTNode<T> temp = null;
while (current != null) {
if (node.data.compareTo(current.data) == 0) {
break;
} else if (node.data.compareTo(current.data) < 0) {
temp = current;
current = current.left;
} else {
current = current.right;
}
}
return temp;
}
}
}