Write the recursive function cca that takes in three parameters -- current, n1,

Question

Write the recursive function cca that takes in three parameters -- current, n1, and n2, that will return the pointer to the closest common ancestor node in the tree rooted at current. Assume both n1 and n2 are pointing valid nodes (which can be the same) in the tree, thus there should be a non-null return value. Also assume that the values in the tree are unique.

struct Node {

int val;

Node *left; // left child, NULL if none

Node *right; // right child, NULL if none

};

Node *cca(Node *current, const Node *n1, const Node *n2) {

}

Explanation / Answer

Following is the recursive function that returns the closest ancestor node in the tree rooted at current:-

Code:-

Node *cca(Node *current, const Node *n1, const Node *n2)
{

// if current points to NULL means it did not have any children, then return NULL
if(current == NULL)
return NULL;

if(n1 == current || n2 == current)
return current;

// recursively call left subtree
Node *left =cca(current->left, n1, n2);

// recursively call right subtree
Node *right = cca (current->right, n1, n2);

if(left != NULL && right != NULL)
return current;

if(left != NULL)
return left;

return right;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.