Lowest common ancestor in a tree

What is the ancestor of a node?

1. An ancestor of a node is any other node on the path from the node to the root.
2. A descendant is the inverse relationship of an ancestor
3. A node v1is a descendant of a node v2if and only if v2is an ancestor of v1.

What is the lowest common ancestor of two nodes v1& v2?

1. The lowest node vin the tree that has both v1and v2as descendants.
2. A vertex vthat lies on the path from the root to v1and the path from the root to v2and the vertex should be the lowest.
3. The desired node v is the bottom ancestor of v1 and v2
4. It is obvious that the lowest common ancestor lies on the shortest path from v1 to v2 .
5. Also, if v1 is ancestor of v2 then v1 is the lowest common ancestor.

One query vs list of queries

There are two flavors of finding lca.

1. Find lca for the given single query i.e.v1 and v2 node
2. Find lca for the given list of queries i.e. [{v1,v2},{v3,v4}.....{vn-1,vn}]

Binary tree and one-time LCA query

Variation # 1: LCA of a normal binary tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

Here for for p = 7, q = 0, lca is 3 .

Approach 1: Using two path stacks for each v1 and v2

1. Search for v1 and add all the nodes in the path to the stack1 .
2. Search for v2 and add all the nodes in the path to the stack2 .
3. Remove the nodes in the stack which has a higher size to keep the same size.
4. Keep popping both stacks until find the same node.
5. The same node is the answer.

Following is the code to implement this approach.

const hasPath = (root, target) => {
    const stack = [];
    const dfs = node => {
        // base case: null node
        if (!node) {
            return false;
        }
        // Capture node in path
        stack.push(node);
        // if match then return
        if (node.val === target.val) {
            return true;
        }
        // if node is found in either left or right subtree then return true
        if (dfs(node.left) || dfs(node.right)) {
            return true;
        }
        // not found in either left or right then remove from path
        stack.pop();
        return false;
    }
    dfs(root);
    return stack;
}
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
    const path1 = hasPath(root, p);
    const path2 = hasPath(root, q);
    // remove extra nodes from bigger stack
    while (path1.length !== path2.length) {
        if (path1.length > path2.length) {
            path1.pop();
        } else {
            path2.pop();
        }
    }
    // find the common node in both stack
    while(path1[path1.length-1].val !== path2[path2.length-1].val) {
        path1.pop();
        path2.pop();
    }
    return path1.pop(); // last one is ans
}; 

Approach 2: Using common parent

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/description/

1. First, find out the parent relationship for each node.
2. Now, the goal is to start traversing from v1 and v2 and find out the intersection node.
3. We can build a visited set for v1 path till root.
4. Now while traversing v2 path, the first node found visited is the common node.

/**
 * @param {Node} node
 * @return {Node}
 */
var lowestCommonAncestor = function (p, q) {
    // Pase 1: Traverse p to build visited set
    const visited = new Set();
    while (p) {
        visited.add(p)
        p = p.parent;
    }
    // Phase 2: traverse q until find node in visited set
    while (q) {
        if (visited.has(q)) {
            return q;
        }
        q = q.parent;
    }
};

Approach 3: Count the occurrence of v1 or v2 in the subtree

1. For each node, we can count if v1 or v2is found either on the left or right or maybe it is the same node. Return the count of nodes found.
2. We can use dfs(node) which will return the number of nodes in it's subtree equal to either v1 or v2 .
3. Since we want to find out the lowest ancestor therefore we need to run postorder traversal i.e. for each node, first scan the left subtree then the right subtree, and then come back to the same node for processing.
4. Since dfs(node) return the count therefore to find out the answer we need to track it using the global variable ans . Also, since we want to return the lowest ancestor therefore first time when we find the answer then we should return it.

Following is the code to implement it.

var lowestCommonAncestor = function(root, p, q) {
    let ans = null;
    const dfs = node => {
        // base case: null node or ans is already found
        if(!node || ans) {
            return 0;
        }
        const left = dfs(node.left, p, q);
        const right = dfs(node.right, p, q);
        const current = ((node.val === p.val) || (node.val === q.val))? 1: 0;
        const total = left + right + current;
        if(total == 2 && !ans) {
            ans = node;
        }
        return total;
    }
    dfs(root);
    return ans;
};

Approach 4: Search node in the left or right subtree

Following is intuition to solve this problem.

1. While running the dfs, if the current node is one of the search nodes then return the current node as the answer i.e. stop traversing dfs further.
2. Search nodes in the left subtree.
3. Search nodes in the right subtree.
4. If it is found in both the left and subtree then the current node is the answer.
5. If it is found in the left tree then the left node is the answer.
6. Otherwise, the right node is the answer.

We can write code as below.

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
    const set = new Set([p.val, q.val]);
    const dfs = node => {
        if (!node) {
            return;
        }
        if (set.has(node.val)) {
            return node;
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (left && right) {
            return node;
        }
        return left ? left : right;
    }
    return dfs(root);
};

Why this code works?

1. As per problem, both p and q exist in the tree.
2. Therefore if let’s say only left subtree has found the one target node; it means second target node will also be in the left subtree.
3. We don’t need to search for second target node; bcz as per problem it does exist in the tree.

Variation # 2: LCA of a binary search tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

1. Node where p & q diverge is a lca.

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    
    // if both p and q smaller than root then it lives in left
    if(p.val < root.val && q.val < root.val ) {
        return lowestCommonAncestor(root.left, p, q);
    }
    // if both p and q greater than root then it lives in right
    if(p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    // else, p and q lives in either left or right so root is common ancestor
    return root;
};

1123. Lowest Common Ancestor of Deepest Leaves

https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/description/

Here, we need to return the node with the value 2 .

Here we need to return node 5.

The following are intuitions to solve this problem.

1. If the left subtree height is greater, then the result will be in the left subtree as it has the highest depth elements. Therefore we will need to choose an answer from the left subtree.
2. The same rule is applied to the right subtree.
3. If the height of both left and right are equal then the current node is the common ancestor of the deepest leaves.
4. Since node will have to wait for height from left and right therefore we need to apply postorder traversal here.

Note: This is one of the best implementation of post order traversal where we keep track the answer node while traversing the tree.

Following is the code for reference.

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var lcaDeepestLeaves = function (root) {
    const dfs = (node) => { // Return lca node with height
        // Base case: null node will have height 0
        if (!node) {
            return [node, 0];
        }
        const [left, heightLeft] = dfs(node.left);
        const [right, heightRight] = dfs(node.right);
        const height = Math.max(heightLeft, heightRight) + 1;
        if (heightLeft === heightRight) {
            return [node, height];
        }

        if (heightLeft > heightRight) {
            return [left, height];
        }
        return [right, height];
    }
    const [node, height] = dfs(root)
    return node;
};

1123. Lowest Common Ancestor of multiple nodes

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/description/

Using Approach 4 discussed for a binary tree for two nodes, we can generalize it to solve this problem (in fact most of the approaches can be generalized).

1. While running the dfs, if the current node is one of the search nodes then return the current node as the answer i.e. stop traversing dfs further.
2. Search nodes in the left subtree.
3. Search nodes in the right subtree.
4. If it is found in both the left and subtree then the current node is the answer.
5. If it is found in the left tree then the left node is the answer.
6. Otherwise, the right node is the answer.

We can write code as below.

/**
 * @param {TreeNode} root
 * @param {TreeNode[]} nodes
 * @return {TreeNode}
 */

var lowestCommonAncestor = function (root, nodes) {
    const set = new Set(nodes.map(v => v.val));
    const dfs = node => {
        if (!node) return
        if (set.has(node.val)) {
            return node;
        }

        const left = dfs(node.left)
        const right = dfs(node.right)
        if (left && right) {
            return node;
        }
        return left ? left : right
    }
    return dfs(root)
};

General tree and multiple LCA query

https://cp-algorithms.com/graph/lca.html

Eular tour of a tree

1. A DFS traversal starts at the root and we build a list eularwhich stores the order of the vertices that we visit.
2. A vertex is added to the eularlist when we first visit it, and after the return of the DFS traversals to its children.
3. This is also called an Euler tour of the tree.

The following is the code for performing an Euler tour of a rooted tree.

// graph: Adjacency list for each node
// root: int to represent the root node
const eularTour = (graph, root) => {
  const n = graph.length;
  const eular = [];
  const visited = new Array(n).fill(0);
  const dfs = node => {
    visited[node] = true;
    eular.push(node);
    for (const neighbor of graph[node]) {
      if(!visited[neighbor]) {
        dfs(neighbor);
        eular.push(node);
      }
    }
  }
  dfs(root);
}

LCA using Eular tour

1. Build an Eular tour path.
2. Build the height of each node along with the Euler tour.
3. Suppose we want to query a pair v1 and v2 for LCA.
4. Find out the first vertex visited by the node v1 in the Euler tour.
5. Find out the first vertex visited by the node v2 in the Euler tour.
6. LCA(v1,v2) is the vertex with the lowest height on this path.
7. Note: LCA between v1 and v2 will be the shortest path between v1 and v2 .
8. There are many algorithms (for example Segment tree, Sqrt decomposition, Sparse table etc) to find out the smallest value in the given range, but for simplicity, we will do a linear scan.

The following is code to implement this approach to find out the lca.

// graph: Adjacency list for each node
// root: int to represent the root node
const lca = (graph, root) => {
  const n = graph.length;
  const eular = [];
  const height = [];
  const visited = new Array(n).fill(0);
  const first = new Array(n).fill(0); // first time seen in eular path
  const dfs = (node, h) => {
    visited[node] = true;
    first[node] = eular.length; // 0th base index, therefore calulcate before push
    eular.push(node);
    height.push(h); // Update height same time as eular to match the index
    for (const neighbor of graph[node]) {
      if(!visited[neighbor]) {
        dfs(neighbor, h + 1);
        eular.push(node);
        height.push(h); // Update height again with eular to match the index
      }
    }
  }
  const query = (p, q) => {
    let left = first[p];
    let right = first[q];
    if(left > right) {
       // swap to keep left smaller than right for easy scan
      [left, right] = [right, left];
    }
    // Scan [left, right] in height to find out the lowest and corresponding node from eualr path
    let min = height[left];
    let ans = eular[left];
    // This linear scan can be improved using SegmentTree etc.
    for (let i=left+1; i <= right; i++) {
      if(height[i] < min) {
        min = height[i];
        ans = eular[i];
      }
    }
    return ans;
  }
  // dfs to build eular, first and height array for each node
  dfs(root, 0);
  // Query for lca
  const ans = query(5,7);
  console.log({ans});
  
}

1257. Smallest Common Region

https://leetcode.com/problems/smallest-common-region/description/

Approach 1: Build a general tree and apply LCA searching for nodes in the subtree

1. Build an adjacency map to represent the tree (graph)
2. The smallest common region will be the lowest common ancestor for the given two regions.

const buildGraph = regions => {
    // Build adjacency map
    const map = new Map();
    for (const nodes of regions) {
        // First region is parent node
        const node = nodes[0];
        if (!map.has(node)) {
            map.set(node, []);
        }
        // Rest is child nodes
        for (let i = 1; i < nodes.length; i++) {
            const child = nodes[i];
            // initialize child
            if (!map.has(child)) {
                map.set(child, []);
            }
            // Add child
            map.get(node).push(child);
        }
    }
    return map;
}

/**
 * @param {string[][]} regions
 * @param {string} region1
 * @param {string} region2
 * @return {string}
 */
var findSmallestRegion = function (regions, region1, region2) {
    const graph = buildGraph(regions);
    const visited = new Set();
    let ans;
    
    const dfsToCalculateLca = node => {
        visited.add(node); // mark node as visited
        let total = (node === region1 || node === region2) ? 1 : 0;
        // process all neighbors
        for (const neighbor of graph.get(node)) {
            if (!visited.has(neighbor)) {
                total += dfsToCalculateLca(neighbor)
            }
        }

        // update gloabal ans only once
        if (!ans && total >= 2) {
            ans = node;
        }
        return total;
    }
    // Launch lca (which is a dfs) to cover disconnected components
    for (const [node] of graph) {
        if (!visited.has(node)) {
            // launch dfs to calculate lca
            dfsToCalculateLca(node);
            if (ans) {
                return ans;
            }
        }
    }
    return '';
};

Approach 2: Build a general tree with parents' relationship and apply LCA using parents

1. Build parent relationship to represent tree (graph).
2. Apply parent-based traversing to find out the lowest common ancestor.

const buildTree = regions => {
    const tree = new Map();
    for (const nodes of regions) {
        const parent = nodes[0];
        // Set parent for child 
        for (let i = 1; i < nodes.length; i++) {
            tree.set(nodes[i], parent);
        }
        // only root will have parent null, check for existnce
        if (!tree.has(parent)) {
            tree.set(parent, null);
        }
    }
    return tree;
}
const findLca = (tree, region1, region2) => {
    // Run LCA to get the common region i.e. find intersection
    const visited = new Set();
    while (region1) {
        visited.add(region1);
        region1 = tree.get(region1);
    }
    while (region2) {
        if (visited.has(region2)) {
            return region2;
        }
        region2 = tree.get(region2);
    }
    return '';
}

/**
 * @param {string[][]} regions
 * @param {string} region1
 * @param {string} region2
 * @return {string}
 */
var findSmallestRegion = function (regions, region1, region2) {
    // Build tree as parent relationship
    const tree = buildTree(regions);
    // Find lca
    return findLca(tree, region1, region2);
};

Happy coding :-)