Find the First Common Ancestor of the two nodes in a binary tree

Problem

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. Node: This is not necessarily a binary search tree.

Solution

I’ll solve this problem without the link to its parent node. This problem can be solved the following steps

1. define the method to check if the subtree of the one node includes target node. I name this method boolean hasNode(Node root, Node target).
2. assume that p and q are the nodes that we want to get their ancestor.
3. define the method to get ancestor of p and q. I name this method Node ancestor(Node root, Node p, Node q).
4. ancestor method can be defined like this.
5. return null, if neither p nor q are not included in root.
6. return root, if root is p or q.
7. return root, if p is included on the other side to q.
8. else, return ancestor(child, p, q)

Source Code