Parent Pointer Approach
Define a function which traverses the binary tree and constructs parent pointers for each node. Traverse from one given node to the root while storing each ancestor in a map. now Traverse from another node to the root and at each step check if the current ancestor of q exists in the parentMap. If found, return the current ancestor as the Lowest Common Ancestor else return null.
Example : To demonstrate finding Lowest Common Ancestor in Binary Tree using Parent Pointer Approach
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
}
}
function ParentPointers(root, parent = null) {
if (root === null) {
return;
}
root.parent = parent;
ParentPointers(root.left, root);
ParentPointers(root.right, root);
}
function lowestCommonAncestor(root, p, q) {
const parentMap = new Map();
// Construct parent pointers
ParentPointers(root);
// Traverse from p to root
// & store the ancestors in map
while (p !== null) {
parentMap.set(p, true);
p = p.parent;
}
while (q !== null) {
if (parentMap.has(q)) {
// return LCA
return q.value;
}
q = q.parent;
}
return null;
}
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
const p = root.right.left;
const q = root.left.right;
console.log(" Lowest Common Ancestor in Binary Tree using Parent Pointer Approach is : ",
lowestCommonAncestor(root, p, q));
Output
Lowest Common Ancestor in Binary Tree using Parent Pointer Approach is : 3
Time complexity: O(n + h) , n is number of nodes and h is height of binary tree
Space complexity: O(h)
LCA in Binary Tree using JavaScript
The lowest common ancestor between two nodes n1 and n2 in a binary tree is defined as the lowest node in a Tree that has both n1 and n2 as descendants. If either n1 or n2 is not present in the tree, or if they are not connected through a common ancestor, the LCA of the binary tree is NULL. Below is an example to understand the LCA of the binary tree clearly.
There are several approaches available in JavaScript to find Lowest Common Ancestor in Binary Tree which are as follows:
Table of Content
- Recursive Approach
- Parent Pointer Approach
Contact Us