236. Lowest Common Ancestor of a Binary Tree


  • 0
    H

    We can find the lowest common ancestor of a Binary Tree in three ways.
    Method 1: Find the paths to both the nodes p and q. Then compare the paths to find the first diffrence. The node beofre the first difference is the common ancestor.
    Link : GeeksforGeeks
    """
    class Solution {

        private List<TreeNode> path1 = new ArrayList<>();
        private List<TreeNode> path2 = new ArrayList<>();
    
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        path1.clear();
        path2.clear();
        return findLCAInternal(root, p, q);
        
    }
    
    private TreeNode findLCAInternal(TreeNode root, TreeNode n1, TreeNode n2) {
    
        if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
            //System.out.println((path1.size() > 0) ? "n1 is present" : "n1 is missing");
            //System.out.println((path2.size() > 0) ? "n2 is present" : "n2 is missing");
            return null;
        }
    
        int i;
        for (i = 0; i < path1.size() && i < path2.size(); i++) {
          //  System.out.println(path1.get(i) + " " + path2.get(i));
            if (!path1.get(i).equals(path2.get(i)))
                break;
        }
    
        return path1.get(i-1);
    }
    
    private boolean findPath(TreeNode root, TreeNode n, List<TreeNode> path)
    {
        if (root == null) {
            return false;
        }
    
        path.add(root);
    
        if (root == n) {
            return true;
        }
    
        if (root.left != null && findPath(root.left, n, path)) {
            return true;
        }
    
        if (root.right != null && findPath(root.right, n, path)) {
            return true;
        }
    
        path.remove(path.size()-1);
    
        return false;
    }
    

    }
    """

    Method 2 : using Recurssion. O(n) time and no extra space.
    """
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        /* Efficient recurssive solution without extra space  O(n) TC
        * Go through the entire tree once, if p is found return p or return null
        * the node with has both left and right not null is the ancestor
        */
        
        // start with chck if tree is null
        if(root == null) return null;
        
        // If any of p or q are root return that
        if(root == p || root == q)
            return root;
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if(left != null && right != null)
            return root;
        
        return (left!=null)?  left : right; 
    }
    

    """
    Method 3: Traverse the tree using BFS. After p and q are on same level move up until you find common ancestor. Using HashMap to store the current pointer and parent, and queue for bfs. Later create a ancestor set to store all the ancestors of p. Then find the common ancestor of p and q.
    """
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        /* Using HashMap to store the parents and 
        find the intersection */
        
        // store current node and parent
        Map<TreeNode, TreeNode> parent = new HashMap();
        // queue for bfs
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        
        parent.put(root, null);
        queue.add(root);
        
        while(!parent.containsKey(p)|| !parent.containsKey(q)) {
            TreeNode node = queue.poll();
            if(node.left != null) {
                parent.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null) {
                parent.put(node.right, node);
                queue.add(node.right);
            }
        }
        // store the set of parents of p
        Set<TreeNode> ancestors = new HashSet<>();
        while(p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        // Just check when p and q can intersect
        while(!ancestors.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }
    

    """


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.