-
Notifications
You must be signed in to change notification settings - Fork 16
Expand file tree
/
Copy pathLCA.test.js
More file actions
51 lines (42 loc) · 1.45 KB
/
Copy pathLCA.test.js
File metadata and controls
51 lines (42 loc) · 1.45 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
// LCA - Lowest Common Ancestor
import Tree from './Tree';
import LCA from './LCA';
function getTree(items) {
var result = Tree();
for (var index = 0; index < items.length; index += 1) {
var item = items[index];
result.add(item.parent, item.id, item);
}
return result;
}
var lca = LCA(getTree([
{ id: 0, parent: null, name: "0" },
{ id: 1, parent: 0, name: "1" },
{ id: 2, parent: 1, name: "2" },
{ id: 3, parent: 1, name: "3" },
{ id: 4, parent: 0, name: "4" },
{ id: 5, parent: 4, name: "5" },
{ id: 6, parent: 4, name: "6" },
{ id: 7, parent: 6, name: "6" },
{ id: 8, parent: 7, name: "8" },
{ id: 9, parent: 3, name: "9" },
{ id: 10, parent: 9, name: "10" }
]));
test('getLowestCommonAncestor test for nodes 2 and 3', () => {
expect(lca.getLowestCommonAncestor(2, 3)).toBe(1);
});
test('getLowestCommonAncestor test for nodes 9 and 10', () => {
expect(lca.getLowestCommonAncestor(9, 10)).toBe(9);
});
test('getLowestCommonAncestor test for nodes 10 and 9', () => {
expect(lca.getLowestCommonAncestor(10, 9)).toBe(9);
});
test('getLowestCommonAncestor test for nodes 5 and 8', () => {
expect(lca.getLowestCommonAncestor(5, 8)).toBe(4);
});
test('getLowestCommonAncestor test for nodes 10 and 8', () => {
expect(lca.getLowestCommonAncestor(10, 8)).toBe(0);
});
test('getLowestCommonAncestor test for nodes 0 and 8', () => {
expect(lca.getLowestCommonAncestor(0, 8)).toBe(0);
});