GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Lowest Common Ancestor · Wilsonlsc/AlgorithmVisualizer@9091313

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • category.json
    • tree/lowest_common_ancestor
      • binary_tree
        • code.js
        • data.js
      • desc.json
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+2-1Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -87,7 +87,8 @@
8787
"tree": {
8888
"list": {
8989
"binary_search_tree": "Binary Search Tree",
90-
"binary_tree_traversal": "Binary Tree Traversal"
90+
"binary_tree_traversal": "Binary Tree Traversal",
91+
"lowest_common_ancestor": "Lowest Common Ancestor"
9192
},
9293
"name": "Tree"
9394
},
Collapse file

‎algorithm/tree/lowest_common_ancestor/binary_tree/code.js‎

Copy file name to clipboard
+25Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
function lcaBT (parent, root, a, b) {
2+
logger._print ('Beginning new Iteration of lcaBT () with parent: ' + parent + ', current root: ' + root);
3+
if (root === -1) {
4+
logger._print ('Reached end of path & target node(s) not found')
5+
return null;
6+
}
7+
8+
if (parent !== null) treeTracer._visit (root, parent)._wait ();
9+
else treeTracer._visit (root)._wait ();
10+
11+
if (root === a || root === b) return root;
12+
13+
var left = lcaBT (root, T [root] [0], a, b);
14+
var right = lcaBT (root, T [root] [1], a, b);
15+
16+
if (left !== null && right !== null) return root;
17+
if (left === null && right === null) {
18+
treeTracer._leave (root, parent)._wait ();
19+
}
20+
21+
return (left !== null ? left : right);
22+
}
23+
24+
var a = 7, b = 9;
25+
logger._print ('Lowest common ancestor of ' + a + ' & ' + b + ' is: ' + lcaBT (null, 5, a, b));
Collapse file

‎algorithm/tree/lowest_common_ancestor/binary_tree/data.js‎

Copy file name to clipboard
+31Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
2+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3+
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
4+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
5+
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
6+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
7+
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
8+
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
9+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
10+
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
11+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
12+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
13+
];
14+
15+
16+
var T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child
17+
[-1,-1],
18+
[ 0, 2],
19+
[-1,-1],
20+
[ 1, 4],
21+
[-1,-1],
22+
[ 3, 8],
23+
[-1, 7],
24+
[-1,-1],
25+
[ 6,10],
26+
[-1,-1],
27+
[ 9,-1]
28+
];
29+
30+
var treeTracer = new DirectedGraphTracer( " Traversal Pre-order ")._setTreeData ( G, 5 );
31+
var logger = new LogTracer ( " Log ");
Collapse file

‎algorithm/tree/lowest_common_ancestor/desc.json‎

Copy file name to clipboard
+15Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
{
2+
"Binary Tree Traversal": "The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root.",
3+
"Applications": [
4+
],
5+
"Complexity": {
6+
"time": "Worst: O(N)",
7+
"space": "Worst: O(1)"
8+
},
9+
"References": [
10+
"<a href='http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/'>GeeksForGeeks</a>"
11+
],
12+
"files": {
13+
"binary_tree": "LCA in a Binary Tree"
14+
}
15+
}

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.