Find Lowest Common Ancestor BST when one or both node (s) do not exist

Question

We can easily use the code to search for LCA in the binary search tree: -

public static Node FindLCA(Node root, Node a, Node b) { if (root == null) return null; if (root.IData == a.IData || root.IData == b.IData) return root; if (root.RightChild != null && (root.RightChild.IData == a || root.RightChild.IData == b)) return root; if (root.LeftChild != null && (root.LeftChild.IData == a || root.LeftChild.IData == b)) return root; if (root.IData > a.IData && root.IData > b.IData) return FindLCA(root.LeftChild, a, b); if (root.IData < a.IData && root.IData < b.IData) return FindLCA(root.RightChild, a, b); else return root; } 

I wonder how to handle if one of the nodes does not exist? One simple possible option: to find nodes in BST - can this be done in O (LogN), and then, if necessary, call FindLCA? Any other options without a preliminary search if the keys exist or not?

EDIT I realized that before I had a few more conditions, added them, and also based on vvijay below.

  20 8 22 4 12 10 14 

Questions:

• But now he does not find the LCA for 8, 22 and says 22 instead of 20.
• Whether LCA (8, 12) will be 8 or 20 - I think it should be 8 based on wiki def LCA (namely, where we allow node to be a descendant of itself).

Any thoughts suggestions.?

Answer 1

I think you can share bad deeds.

 if (root == null) return null; if (root.Idata == a.Idata || root.Idata == b.Idata) return root; 

or just change the null value to return root in your code. Thus, a null return value means that you do not have any of the request nodes in the tree.