-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlcaBST.js
172 lines (132 loc) · 5.4 KB
/
lcaBST.js
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
// Lowest common ancestor of a binary search tree
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
// Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
// According to the definition of LCA on Wikipedia: “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).”
// 6
// 2 8
// 0 4 7 9
// 3 5
// Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
// Output: 6
// Explanation: The LCA of nodes 2 and 8 is 6.
// Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
// Output: 2
// Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
// Input: root node of tree and the two vals we want to look for
// Output: the ancestor (parent) that has both values inside it (either itself or its children have it)
// Strategy:
// Will need to iterate through the tree to find the matching values
// Evaluate the p and q given and determine if we should iterate onto the right or left side
// Use a stack to store parent nodes(ancestors)
// The node itself can be a common ancestor
// When we have found our nodes after iterating, compare out stack of ancestors (parents)
// Return the commonAncestor
// Use two stacks one for p, one for q
// Start from root and find p, as we iterate down the tree add the current node onto the stack
// Same for q
// After finding both nodes, iterate through the longer stack backwards and check against the second stack backwards
// Time Complexity O(n)
// Space Complexity O(n)
// var lowestCommonAncestor = function(root, p, q) {
// let pStack = [];
// let qStack = [];
// let currNode = root; // Set current node to root
// while (currNode !== p) { // Find the p node first
// debugger;
// pStack.push(currNode); // Push parent into our stack
// if (p.val < currNode.val) { // if p is less than curr node (BST)
// //iterate down the left side
// currNode = currNode.left;
// } else {
// currNode = currNode.right;
// }
// }
// pStack.push(currNode); // After we have found it, also push itself onto the stack
// // Now find q node
// currNode = root;
// while (currNode !== q) {
// qStack.push(currNode);
// if (q.val < currNode.val) {
// currNode = currNode.left;
// } else {
// currNode = currNode.right;
// }
// }
// qStack.push(currNode);
// // Make stack equal size and then iterate backwards and check against each other
// if (pStack.length > qStack.length) {
// pStack = pStack.slice(0, qStack.length);
// } else {
// qStack = qStack.slice(0, pStack.length);
// }
// // console.log(pStack);
// // console.log(qStack);
// for (let i = pStack.length - 1; i >= 0; i--) {
// if (pStack[i] === qStack[i]) {
// return pStack[i];
// }
// }
// return null;
// };
// Implementing a recursive approach
// Time complexity is O(log n) because we only have to iterate through half the tree
// Space complexity is O(log n) bc we are only iterating through one half of the nodes (BST)
// const lowestCommonAncestor = function(root, p, q) {
// if (root === null) return null; // Basecase if root is null, just return null (no common ancestor)
// // If the values are both greater than the current root node, recursively iterate to the right side
// if (p.val > root.val && q.val > root.val) {
// return lowestCommonAncestor(root.right, p, q);
// // Else if the values are both lower than the current root node, recursively iterate to the left side
// } else if (p.val < root.val && q.val < root.val) {
// return lowestCommonAncestor(root.left, p, q);
// } else { // Else the current root node will be the least common ancestor
// return root;
// }
// }
// Iterative approach with O(1) space complexity and O(h) time complexity (h is height of tree);
const lowestCommonAncestor = (root, p, q) => {
if (root === null) return null; // Edge case if root is null
while (root) {
if (p.val < root.val && q.val < root.val) { // If both vals are less than, iterate through the left
root = root.left;
} else if (p.val > root.val && q.val > root.val) { // If both vals are greater than iterate through the right
root = root.right;
} else {
return root; // Else we are currently at its LCA.
}
}
}
function TreeNode(val, left, right) {
this.val = val;
this.left = left || null;
this.right = right || null;
}
// let node9 = new TreeNode(9);
// let node7 = new TreeNode(7);
// let node8 = new TreeNode(8, node7, node9);
// let node3 = new TreeNode(3);
// let node5 = new TreeNode(5);
// let node4 = new TreeNode(4, node3, node5);
// let node0 = new TreeNode(0);
// let node2 = new TreeNode(2, node0, node4);
// let node6 = new TreeNode(6, node2, node8);
// let testRoot = node6;
// let result = lowestCommonAncestor(testRoot, node2, node8);
// console.log(result);
// let node1 = new TreeNode(1);
// let node2 = new TreeNode(2, node1);
// console.log(node2);
// let result = lowestCommonAncestor(node2, node2, node1);
// console.log(result);