Write a C++ program In this ques tion you are to design two algorithms to find t

Question

Write a C++ program

In this ques tion you are to design two algorithms to find the lowest (nearest) common ancestor of two given nodes in a binary tree. You may assume that both nodes already exist in the tree These functions have basically the same header, but different names and implementations Algorithm findLCA (rTree, ell, e12) Pre: rTree reference to a Binary Tree el1 :: Element, a data value in the tree el2 :: Element, another data value in the tree Post: tree is unchanged Return: the reference to an element, which is the lowest of common ancestor of the two given values 1. An intuitive algorithm would be to collect the ancestors of both values, and compare them. Remember the limitations of the computer: a binary tree's pointers point down the tree! So while a human might trace the ancestors of a node in a tree diagram, by "walking" against the direction of the arrows in a diagram, a computer cannot do that easily. Instead, you might need to use the List ADT to make lists of all the ancestors of both values (how?) and then search through these two lists to find the first value where they differ Assume in this case that the tree is also a binary search tree. This makes finding the ancestor lists a bit easier than the general case. The general case is still possible if you want a challenge, but it is not required. Call this algorithm findLCA. For brevity, you do not need to define List ADT operations (i.e., you may use operations like insert Head, but you do not have to write out the algorithms for these operations, because we've already done all that work) 2. There is another algorithm that uses the property of a binary search tree to find the lowest common ancestor more efficiently. The lowest common ancestor of the two values is different from other common ancestors (try a few examples, and see if you can disoover this "difference" for yourself). You can use this insight to design an algorithm that is more efficient in binary search trees (but alas cannot be applied to binary trees that do not have the BST property) Call this algorithm findLCA_BST You do not have to handle the error case in which one or both values are not in the tree

Explanation / Answer

LCA Algo

I will write 3 algos -First in terms of easy language , second for part a) and third for part b)

--here Current node is reference of rTree

Algo 1
------------
LCAnode = null
LCA(Node currentNode, Node el1, Node el2) //function
{
if currentNode is null then return 0 or -1 whatever u wish
so currentValue = 0
if (currentNode is el1 || currentNode is el2)
then currentValue = 1
leftValue = LCA(currentNode.left, el1, el2)
rightValue = LCA(currentNode.right, el1, el2);
if ((currentValue is 1 && leftValue is 1)
||(currentValue is 1 && rightValue is 1)
||(leftValue is 1 && rightValue is 1))
{
LCANode = currentNode;
return 2;
}
return currentValue + leftValue + rightValue;
}

Algo 2
----------

/* A path needs to be discovered from base/root node to destination node of the binary tree,
Store the desired path in vector path[], and true is returned if path exists otherwise false */

bool discoverPath(Node *root, vector<int> &path, int x)
{
  
if (root == NULL) return false;

/* The node will be removed if not in path from root to x */

path.push_back(root->key);

/* See if the x is same as root's key */

if (root->key == x)
return true;

/* if x is found in left or right sub-tree */
if ( (root->left && discoverPath(root->left, path, x)) ||
(root->right && discoverPath(root->right, path, x)) )
return true;

/* If not present in subtree rooted with root, remove root from path[] and return false */
path.pop_back();
return false;
}

/* Returns LCA if node el1, el2 are present in the given binary tree, otherwise return -1*/
int discoverLCA(Node *root, int el1, int el2)
{
  
vector<int> path1, path2;

// discover paths, if no path found, return -1
if ( !discoverPath(root, path1, el1) || !discoverPath(root, path2, el2))
return -1;

/* Compare the paths to get the first different value */
int i;
for (i = 0; i < path1.size() && i < path2.size() ; i++)
if (path1[i] != path2[i])
break;
return path1[i-1];
}

Algo 3
--------

For LCABest we use here one single traversal using pointers

*discoverLCABest(struct Node* root, int el1, int el2)
{
  
if (root == NULL) return NULL;

/* (Note that if a key is ancestor of other, then the ancestor key becomes LCABest */
if (root->key == el1 || root->key == el2)
return root;


Node *left_LCABest = discoverLCABest(root->left, el1, el2);
Node *right_LCABest = discoverLCABest(root->right, el1, el2);

/* If both of the above return Not-NULL, then one key is present in one subtree and other is present in other,
So this node is the LCABest*/

if (left_LCABest && right_LCABest) return root;

// Otherwise check if left subtree or right subtree is LCABest
return (left_LCABest != NULL)? left_LCABest: right_LCABest;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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