-
Notifications
You must be signed in to change notification settings - Fork 41
/
LowestCommonAncestorOfABinarySearchTree.java
151 lines (123 loc) · 4.98 KB
/
LowestCommonAncestorOfABinarySearchTree.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
package LeetCodeJava.BinarySearchTree;
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
import LeetCodeJava.DataStructure.TreeNode;
/**
* LCA :
* “The lowest common ancestor is
* defined between two nodes p and q as the lowest node
* in T that has both p and q as descendants
* (where we allow a node to be a descendant of itself).”
*
*/
/** NOTE !!!
*
* Binary Search Tree (BST) property :
* -> For each node
* - `left sub node < than current node`
* - `right sub node > than current node`
*
*
* (From LC)
* Lets review properties of a BST:
*
* - Left subtree of a node N contains nodes whose values are lesser than or equal to node N's value.
* - Right subtree of a node N contains nodes whose values are greater than node N's value.
* - Both left and right subtrees are also BSTs.
*
*/
public class LowestCommonAncestorOfABinarySearchTree {
class Solution {
// V0
// IDEA : RECURSIVE + BST PROPERTY
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// if root equals p or q, return root as LCA
if (root.equals(p) || root.equals(q)) {
return root;
}
/** NOTE !!! BST property : right > root > left */
// search on right sub tree
if (p.val > root.val && q.val > root.val){
return this.lowestCommonAncestor(root.right, p, q);
}
// search on left sub tree
if (p.val < root.val && q.val < root.val){
return this.lowestCommonAncestor(root.left, p, q);
}
// p, q are in different side (sub tree), then return root as LCA directly
return root;
}
// V0'
// IDEA : RECURSIVE + BST PROPERTY
public TreeNode lowestCommonAncestor_0(TreeNode root, TreeNode p, TreeNode q) {
// below logic is optional
if (root == null || root == p || root == q){
return root;
}
// BST property : right child always > root val
if (root.val < p.val && root.val < q.val){
/** NOTE !!! we need to return recursive call below
*
* -> e.g. return lowestCommonAncestor(root.right, p, q) instead of lowestCommonAncestor(root.right, p, q)
*/
return lowestCommonAncestor_0(root.right, p, q);
// BST property : left child always < root val
}else if (root.val > p.val && root.val > q.val) {
/** NOTE !!! we need to return recursive call below
*
* -> e.g. return lowestCommonAncestor(root.right, p, q) instead of lowestCommonAncestor(root.right, p, q)
*/
return lowestCommonAncestor_0(root.left, p, q);
}else{
return root;
}
}
// V1
// IDEA : Recursive Approach
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/editorial/
public TreeNode lowestCommonAncestor_2(TreeNode root, TreeNode p, TreeNode q) {
// Value of current node or parent node.
int parentVal = root.val;
// Value of p
int pVal = p.val;
// Value of q;
int qVal = q.val;
if (pVal > parentVal && qVal > parentVal) {
// If both p and q are greater than parent
return lowestCommonAncestor_2(root.right, p, q);
} else if (pVal < parentVal && qVal < parentVal) {
// If both p and q are lesser than parent
return lowestCommonAncestor_2(root.left, p, q);
} else {
// We have found the split point, i.e. the LCA node.
return root;
}
}
// V2
// IDEA : Iterative Approach
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/editorial/
public TreeNode lowestCommonAncestor_3(TreeNode root, TreeNode p, TreeNode q) {
// Value of p
int pVal = p.val;
// Value of q;
int qVal = q.val;
// Start from the root node of the tree
TreeNode node = root;
// Traverse the tree
while (node != null) {
// Value of ancestor/parent node.
int parentVal = node.val;
if (pVal > parentVal && qVal > parentVal) {
// If both p and q are greater than parent
node = node.right;
} else if (pVal < parentVal && qVal < parentVal) {
// If both p and q are lesser than parent
node = node.left;
} else {
// We have found the split point, i.e. the LCA node.
return node;
}
}
return null;
}
}
}