Lowest Common Ancestor

Komal Dua · Komal Dua · commit 5a836cdfb168 · 2016-06-04T11:26:08.000+05:30
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -87,7 +87,8 @@
    "tree": {
       "list": {
          "binary_search_tree": "Binary Search Tree",
-         "binary_tree_traversal": "Binary Tree Traversal"
+         "binary_tree_traversal": "Binary Tree Traversal",
+         "lowest_common_ancestor": "Lowest Common Ancestor"
       },
       "name": "Tree"
    },
@@ -97,4 +98,4 @@
       },
       "name": "Uncategorized"
    }
-}
+}
diff --git a/algorithm/tree/lowest_common_ancestor/binary_tree/code.js b/algorithm/tree/lowest_common_ancestor/binary_tree/code.js
@@ -0,0 +1,25 @@
+function lcaBT (parent, root, a, b) {
+    logger._print ('Beginning new Iteration of lcaBT () with parent: ' + parent + ', current root: ' + root);
+    if (root === -1) {
+        logger._print ('Reached end of path & target node(s) not found')
+        return null;
+    }
+    
+    if (parent !== null) treeTracer._visit (root, parent)._wait ();
+    else treeTracer._visit (root)._wait ();
+    
+    if (root === a || root === b) return root;
+    
+    var left = lcaBT (root, T [root] [0], a, b);
+    var right = lcaBT (root, T [root] [1], a, b);
+    
+    if (left !== null && right !== null) return root;
+    if (left === null && right === null) {
+        treeTracer._leave (root, parent)._wait ();
+    }
+    
+    return (left !== null ? left : right);
+}
+
+var a = 7, b = 9;
+logger._print ('Lowest common ancestor of ' + a + ' & ' + b + ' is: ' + lcaBT (null, 5, a, b));
diff --git a/algorithm/tree/lowest_common_ancestor/binary_tree/data.js b/algorithm/tree/lowest_common_ancestor/binary_tree/data.js
@@ -0,0 +1,31 @@
+var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
+];
+
+
+var T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child
+        [-1,-1],
+        [ 0, 2],
+        [-1,-1],
+        [ 1, 4],
+        [-1,-1],
+        [ 3, 8],
+        [-1, 7],
+        [-1,-1],
+        [ 6,10],
+        [-1,-1],
+        [ 9,-1]
+];
+
+var treeTracer = new DirectedGraphTracer( " Traversal Pre-order ")._setTreeData ( G, 5 );
+var logger = new LogTracer ( " Log ");
diff --git a/algorithm/tree/lowest_common_ancestor/desc.json b/algorithm/tree/lowest_common_ancestor/desc.json
@@ -0,0 +1,15 @@
+{
+  "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.",
+  "Applications": [
+  ],
+  "Complexity": {
+    "time": "Worst: O(N)",
+    "space": "Worst: O(1)"
+  },
+  "References": [
+    "<a href='http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/'>GeeksForGeeks</a>"
+  ],
+  "files": {
+    "binary_tree": "LCA in a Binary Tree"
+  }
+}
