Find Common Ancestor
Problem: find the common ancestor of two nodes in a tree
Given a "tree" pointer pointing to the root node of a tree and the other two pointers to two nodes in the tree. You are expected to write a C++ subroutine to find the common ancestor of the two nodes. In any unexpected condition, your code should return null pointer and avoid crashing.
For example, if the tree is like below, B is the common ancestor of E and G; A is the common ancestor of H and F; D is the common ancestor of D and G.
gailya 20:30:17
You are allowed to use recursion but as few as possible. You are NOT allowed to use STL. Please follow the type definitions shown below:
//tree node type
typedef struct _Node
...{
char value;
struct _Node* left;
struct _Node* right;
}Node;
class CommonNodeFinder
...{
//add any auxiliary code here as you wish.
public:
inline Node* FindCommonAncestor(Node* tree, Node* node_1, Node* node_2)
...{
//your code here.
}
}