CODEWITHSUNDEEP
javaalgorithmbinary-treelowest-common-ancestor
user2426823
user2426823

Reputation:

How to implement lowest common ancestor for a binary tree using Java?

I encountered the following implementation and spent some time, but still can't grasp the idea. Could someone please explain line by line what it is doing? I just don't understand at what point it can decide a node is an ancestor.

Thank you 

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || 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;
    }
}

Upvotes: 5

Views: 849

Answers (4)

Saurav Sahu
Saurav Sahu

Reputation: 13994

The basic idea behind marking the presence of a number in a tree branch is to use the non-null pointer for number FOUND, and null pointer for NOTFOUND.

The call stack winds back once a number (p or q) is found, or when the root is null. Later one gives a clear indication of absence of the searched number.

There are four possible scenarios:

1.) Both under one parent.

                      root
                      /  \ 
            Leftsubtree  Rightsubtree
                p/q        q/p

In this case, in the below code, a moment would come when this is satisfied if(left != null && right != null) return root;

2.) One parent of other.

      q/p                     p/q
      /            OR          \ 
Leftsubtree                 Rightsubtree
  p/q                           q/p

In this case, this will be satisfied if(root == null || root == p || root == q) return root;

3.) Either of them not present in the tree. This condition would go undetected. As shown in case#2, the function returns immediately without further traversing and looking for its counterpart in the tree below it.

4.) None of them are present in the tree.

First line if(root == null ... return ; will be executed for each non-existing child. The final result would be null return, as none of the number would ever be found.

Line by line code explanation.

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

    /* (root == null)  This proves that root is not in the branch of tree of our interest. Returning null would means NOTFOUND.*/
    /* (root == p || root == q) either p or q or both are found. Returning non-null root would means FOUND. */

    /*Check for presence in leftsubtree */
    TreeNode left = lowestCommonAncestor(root.left, p, q);

    /*Check for presence in rightsubtree */
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    /*            root
                  /  \ 
        leftsubtree  Rightsubtree
            p/q        q/p

    */
    if(left != null && right != null)   return root; //both the numbers are found inside tree under root 

    // left or right subtree OR both don't have p or q. Return the overall find result under root.
    return left != null ? left : right;
}

Upvotes: 3

shawn
shawn

Reputation: 460

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // root == null (no root no LCA)
    // root == p || root == q (if either p or q is the root then root is LCA)
    if(root == null || root == p || root == q)  return root;
    //get the LCA of p and q in left sub tree
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    //get the LCA of p and q in right sub tree
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // if one of p or q is in left subtree and another is in the right subtree, 
    //then the root is the LCA
    if(left != null && right != null)   return root;
    // if left is not null, left is LCA, else right is LCA 
    return left != null ? left : right;
}

Upvotes: 1

johnson
johnson

Reputation: 131

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root->val == p->val || root->val == q->val ||
        (p->val < root->val && root->val < q->val) ||
        (q->val < root->val && root->val < p->val)) {
        return root;
        }
    else if (root->val < p->val) return lowestCommonAncestor(root-> right, p, q);
    else return lowestCommonAncestor(root->left, p, q);

Here is my answer in C++, but should be very similar as long as you switch the '->' to '.' syntax. It's a recursive function where it checks the current leaf with its left and right children and once the first if statement conditions are true, it means it identified the lowest common ancestor because if either of its children are bigger, it means that it is the smallest value.

For example: given 2 as its root and 1 and 4 as its children(left and right respectively), 1 is lower than root, but 4 is not, so 2 is the smallest common denominator. IT would stop at the first run.

If you draw yourself a binary tree and test out each step it will make much more sense.

Upvotes: 0

nail fei
nail fei

Reputation: 2329

if(root == null || root == p || root == q)  return root;

if current root node is null then at current sub_tree there doesnt exist the common ancestor of p and q, so return null root==null

and if p or q equals root. I assume p=root and here as for q, it is either the offspring of p or not offspring of p, however which case, there are no need to travese the sub_tree of p, for if the former case p is ancestor of q so just return p p==root, else return p directly, it dont produce error although in this case p is not ancestor of q.
for the statement
if(left != null && right != null) return root; and I will explain it later.

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

now there are exist several possible things:
1. the p and q are all offspring of root.left
2. the p and q are all offspring of root.right
3. these two node one is offspring of root.left the other is offspring of root.right

these two recursive statement are used to find the common ancestor of p and q (for 1,2) else used to find p and q (for 3)

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

this statement is used to process the corresponding result of 3, the p and q exist the left_subtree and right_suntree of root, so ancestor is root

 return left != null ? left : right;

this statement is used to process corresponding result of 1,2, pand q exist same sub_tree either left or right.

Upvotes: 0

Related Questions