forked from aishraj/JavaScript-Interview-Questions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path008.js
More file actions
120 lines (108 loc) · 2.92 KB
/
Copy path008.js
File metadata and controls
120 lines (108 loc) · 2.92 KB
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
/*
* <!--
* This program is distributed under
* the terms of the MIT license.
* Please see the LICENSE file for details.
* -->
*/
/*
* Devise an algorithm to find the lowest common ancestor of a binary search
* tree, given two nodes. You may assume that both nodes are members of the
* tree.
* Use the Node structure in 007.js
*/
/*____________________________________________________________________________*/
/**
* @class {public} Node
*
* A typical binary tree node.
*
* @param {Node} left - the left node.
* @param {Node} right - the right node.
* @param {Integer} value - the value of this node.
*/
function Node(left, right, value) {
this.left = left;
this.right = right;
this.value = value;
}
/*
* Sample tree structure.
*/
var root = new Node(
new Node(
new Node(null, null, 28),
new Node(null, null, 79),
62
),
new Node(
new Node(
new Node(null, null, 121),
null,
130),
new Node(null, null, 190),
141
),
110
);
/**
* @function {public static} findLowestCommonAncestor
*
* Finds the lowest common ancestor between two nodes.
*
* @param {Node} root - the root node.
* @param {Integer} value1 - the left value.
* @param {Integer} value2 - the right value.
*
* @return the found node, if any; `null` otherwise.
*/
function findLowestCommonAncestor(root, value1, value2) {
var current = root;
var value = null;
while (current != null) {
value = current.value;
if (value > value1 && value > value2) {
current = current.left;
} else if (value < value1 && value < value2) {
current = current.right;
} else {
return current;
}
}
return null;
}
/*____________________________________________________________________________*/
console.log( findLowestCommonAncestor(root, 121, 190) );
console.log( findLowestCommonAncestor(root, 28 , 190) );
console.log( findLowestCommonAncestor(root, 28 , 79 ) );
console.log( findLowestCommonAncestor(root, 62 , 141) );
/*
Output: ($ /usr/bin/node 008.js)
{ left:
{ left: { left: null, right: null, value: 121 },
right: null,
value: 130 },
right: { left: null, right: null, value: 190 },
value: 141 }
{ left:
{ left: { left: null, right: null, value: 28 },
right: { left: null, right: null, value: 79 },
value: 62 },
right:
{ left: { left: [Object], right: null, value: 130 },
right: { left: null, right: null, value: 190 },
value: 141 },
value: 110 }
{ left: { left: null, right: null, value: 28 },
right: { left: null, right: null, value: 79 },
value: 62 }
{ left:
{ left: { left: null, right: null, value: 28 },
right: { left: null, right: null, value: 79 },
value: 62 },
right:
{ left: { left: [Object], right: null, value: 130 },
right: { left: null, right: null, value: 190 },
value: 141 },
value: 110 }
*/