What is the Lowest Common Ancestor?

In a tree, the lowest common ancestor (LCA) of two nodes, n1 and n2, is the shared ancestor located farthest from the root and has both n1 and n2 as descendants.

Properties of the Lowest Common Ancestor:

1. An LCA can be one of the input nodes themselves if one is an ancestor of the other.
2. The LCA is a shared ancestor, meaning both nodes should have a path from the root to the LCA.
3. The LCA is the deepest node that is a common ancestor. It is located farthest from the root.
4. For a binary tree, the LCA can be an internal node or a leaf node.

Application of LCA (Lowest Common Ancestor):

The Lowest Common Ancestor (LCA) concept has various applications:

1. Binary Trees: LCA is frequently used in binary tree-related problems, such as finding the distance between two nodes, determining the level of a node, or solving problems involving the relationship between nodes in a binary tree.
2. Graphs: LCA can be applied to general graphs as well. In a directed or undirected graph, the LCA of two nodes can be useful in determining their closest common ancestor or solving problems related to the relationship between nodes.
3. XML Processing: LCA can be utilized in XML processing to find the least common ancestor of multiple elements or to determine the structural relationships between XML elements.
4. Network Routing: LCA can be used in network routing algorithms to determine the common ancestor or shared point in a network where multiple paths converge.

Common approaches to find LCA of two nodes in a tree:

Recursive Approach:

• This is the most straightforward and commonly used approach.
• Start from the root and recursively search for the LCA in the left and right subtrees.
• If one node is found in the left subtree and the other in the right subtree, the current node is the LCA.
• If both nodes are found in the left subtree, recursively search in the left subtree.
• If both nodes are found in the right subtree, recursively search in the right subtree.
• Repeat the process until the LCA is found or the entire tree is traversed.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class LowestCommonAncestor {

    public TreeNode findLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = findLowestCommonAncestor(root.left, p, q);
        TreeNode right = findLowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }

    public static void main(String[] args) {
        // Create the tree:
        //        3
        //       / \
        //      5   1
        //     / \ / \
        //    6  2 0  8
        //      / \
        //     7   4

        TreeNode 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.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode n1 = root.left;  // Node with value 5
        TreeNode n2 = root.right; // Node with value 1

        LowestCommonAncestor lca = new LowestCommonAncestor();
        TreeNode result = lca.findLowestCommonAncestor(root, n1, n2);
        System.out.println(result.val);  // Output: 3
    }
}

In this Java implementation, we have a TreeNode class to represent the nodes of the tree. The findLowestCommonAncestor method recursively searches for the LCA in the left and right subtrees, following the steps mentioned in the recursive approach. The main method demonstrates the usage by creating a tree and finding the LCA of two nodes.

• The time complexity of this approach is O(N), where N is the number of nodes in the tree.
• The space complexity of this approach is O(H), where H is the height of the tree.

Iterative Approach:

• Start by assigning parent pointers to each node in the tree, indicating the parent of each node.
• Create a set or a hash table to keep track of visited nodes.
• Traverse from the first node (n1) towards the root, marking each visited node in the set.
• Traverse from the second node (n2) towards the root, checking if each visited node exists in the set. The first common node encountered is the LCA.
• Return the LCA as the result.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode parent;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class LowestCommonAncestor {

    public TreeNode findLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Assign parent pointers
        assignParentPointers(root, null);

        Set<TreeNode> visited = new HashSet<>();

        // Traverse from n1 towards the root, marking visited nodes
        while (p != null) {
            visited.add(p);
            p = p.parent;
        }

        // Traverse from n2 towards the root, checking visited nodes
        while (q != null) {
            if (visited.contains(q)) {
                return q;
            }
            q = q.parent;
        }

        return null;
    }

    private void assignParentPointers(TreeNode node, TreeNode parent) {
        if (node != null) {
            node.parent = parent;
            assignParentPointers(node.left, node);
            assignParentPointers(node.right, node);
        }
    }

    public static void main(String[] args) {
        // Create the tree:
        //        3
        //       / \
        //      5   1
        //     / \ / \
        //    6  2 0  8
        //      / \
        //     7   4

        TreeNode 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.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode n1 = root.left;  // Node with value 5
        TreeNode n2 = root.right; // Node with value 1

        LowestCommonAncestor lca = new LowestCommonAncestor();
        TreeNode result = lca.findLowestCommonAncestor(root, n1, n2);
        System.out.println(result.val);  // Output: 3
    }
}

In this Java implementation, we have a TreeNode class to represent the nodes of the tree. The findLowestCommonAncestor method implements the iterative approach by assigning parent pointers to each node in the tree and then traversing from the given nodes (n1 and n2) towards the root, using the parent pointers. The first common visited node encountered is the Lowest Common Ancestor (LCA). The main method demonstrates the usage by creating a tree and finding the LCA of two nodes.

• The time complexity of this approach is O(N), where N is the number of nodes in the tree. In the worst case, the algorithm needs to traverse from both given nodes (n1 and n2) to the root. Each traversal takes at most O(N) time, as it visits each node at most once. Therefore, the overall time complexity is linear with respect to the number of nodes.
• The space complexity of this approach is O(N), where N is the number of nodes in the tree.

Note: also read about Binary Search Tree (BST)

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py