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.
I’ll solve this problem without the link to its parent node. This problem can be solved the following steps
- 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).
- assume that
qare the nodes that we want to get their ancestor.
- define the method to get ancestor of p and q. I name this method
Node ancestor(Node root, Node p, Node q).
- ancestor method can be defined like this.
- return null, if neither p nor q are not included in root.
- return root, if root is p or q.
- return root, if p is included on the other side to q.
- else, return ancestor(child, p, q)