Approach
To calculate the ancestor's vector's dot product, we've to first find these vectors. Because both values 'VAL1' and 'VAL2' could be in any of the trees, in the worst-case scenario, we'll have to search both trees. Once we have these ancestor's vectors, we'll loop through them and find the dot product.
Let's see how to implement this. We'll have two functions: caculateDotProduct(), which will calculate the dot product, and getAncestorPath(), which will find the ancestor's vector. Now let's see how these functions work.
calculateDotProduct()
Parameters
- ‘ROOT1’ - Root of the first tree.
- ‘ROOT2’ - Root of the second tree.
- ‘VAL1’ - First value.
- ‘VAL2’ - Second value.
Working
- If both trees are empty, i.e., 'ROOT1 = NULL' and 'ROOT2 = NULL', return zero.
- Next, declare two vectors, 'VEC1' and 'VEC2', for storing the ancestor's vector for 'VAL1' and 'VAL2'.
- After that, we search the first tree for 'VAL1'. If our search is successful, we don't search in the second tree. Else we do.
- The same is done for 'VAL2.'
- Now, we have 'VEC1' (ancestors of 'VAL1') and 'VEC2'(ancestors of 'VAL2').
- Now loop through the vectors and add their product into the ‘ANSWER’ until one of them is empty.
getAncestorPath()
Parameters
- ‘ROOT’ - Root of the tree.
- ‘VAL’ - Value to be searched.
- ‘VEC’ - Vector to store the ancestor’s vector.
- 'TEMP' - Temporary vector for backtracking.
Working
- Base Case - If ‘ROOT = NULL’, return false.
- Found Case - We check if the current ROOT->DATA is equal to 'VAL,' then store the 'TEMP' vector in 'VEC' and return true.
- If we've not found the 'VAL,' then insert the current tree node value in 'TEMP' and search in the left and right subtree.
- If we found 'VAL' in any of the subtrees, return true.
- Backtracking - Else pop the current node's value from 'TEMP', and return false.
Now that we’ve defined the functions let’s try to code them.
Program
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Class for Tree Nodes.
class TreeNode
{
public:
int data;
// Pointer to the left node.
TreeNode *left;
// Pointer to the right node.
TreeNode *right;
// Constructor.
TreeNode(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};
// Function that finds the ancestors for a given node in the tree.
bool getAncestorPath(TreeNode *root, int val, vector<int> &vec, vector<int> temp)
{
// If 'ROOT' is null, return false.
if (root == NULL)
return false;
// If we've found the value in the tree, store the ancestor's array in 'VEC' and return true.
if (root->data == val)
{
vec = temp;
return true;
}
// Insert the current 'ROOT->DATA' into the 'TEMP' vector.
temp.emplace_back(root->data);
// Check if 'VAL' is present in left subtree then return true.
if (getAncestorPath(root->left, val, vec, temp))
return true;
// Check if 'VAL' is present in right subtree then return true.
if (getAncestorPath(root->right, val, vec, temp))
return true;
// Backtrack.
temp.pop_back();
// Return false if 'VAL' is not present.
return false;
}
// Function that calculates the dot product of ancestors of two given nodes.
int calculateDotProduct(TreeNode *root1, TreeNode *root2, int val1, int val2)
{
// If both trees are empty, return 0.
if (root1 == NULL && root2 == NULL)
return 0;
// Declare 'VEC1' and 'VEC2' for storing the ancestors of 'VAL1' and 'VAL2', respectively.
vector<int> vec1, vec2;
// Getting ancestors' path for 'VAL1'.
if (!getAncestorPath(root1, val1, vec1, {}))
getAncestorPath(root2, val1, vec1, {});
// Getting ancestors’ path for 'VAL2'
if (!getAncestorPath(root1, val2, vec2, {}))
getAncestorPath(root2, val2, vec2, {});
// Calculating dot product.
int i = 0, j = 0, answer = 0;
while (i < vec1.size() && j < vec2.size())
{
answer += vec1[i] * vec2[j];
i++;
j++;
}
// Return answer.
return answer;
}
// Function to create binary tree.
TreeNode *takeInput()
{
int rootData;
cin >> rootData;
if (rootData == -1)
{
return NULL;
}
TreeNode *root = new TreeNode(rootData);
queue<TreeNode *> q;
q.push(root);
while (!q.empty())
{
TreeNode *currentNode = q.front();
q.pop();
int leftChild, rightChild;
cin >> leftChild;
if (leftChild != -1)
{
TreeNode *leftNode = new TreeNode(leftChild);
currentNode->left = leftNode;
q.push(leftNode);
}
cin >> rightChild;
if (rightChild != -1)
{
TreeNode *rightNode = new TreeNode(rightChild);
currentNode->right = rightNode;
q.push(rightNode);
}
}
return root;
}
int main()
{
cout << " Enter the values of nodes in the first binary tree in level order fashion (-1 for NULL): ";
TreeNode *root1 = takeInput();
cout << " Enter the values of nodes in the second binary tree in level order fashion (-1 for NULL): ";
TreeNode *root2 = takeInput();
cout << "Enter the values of VAL1 and VAL2: ";
int val1, val2;
cin >> val1 >> val2;
int dotProduct = calculateDotProduct(root1, root2, val1, val2);
cout << "Dot product of ancestors of " << val1 << " and " << val2 << " nodes is: " << dotProduct << endl;
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Input
Enter the values of nodes in the first binary tree in level order fashion (-1 for NULL): 1 7 3 11 -1 4 10 -1 22 -1 -1 -1 -1 -1 -1
Enter the values of nodes in the second binary tree in level order fashion (-1 for NULL): 0 2 6 5 16 -1 20 27 -1 33 -1 -1 -1 -1 -1 -1 -1
Enter the values of VAL1 and VAL2: 20 4
Output
Dot product of ancestors of 20 and 4 nodes is: 18
Complexities
Time Complexity
O(N + M), where 'N' is the first tree's size, and 'M' is the second.
We'll have to scan both trees independently for 'VAL1' and 'VAL2"s ancestors in the worst-case scenario. As a result, this will require O(2*(N + M)) or O(N + M) time.
Space Complexity
O(N+M), where 'N' is the first tree's size, and 'M' is the second.
We are declaring two vectors, 'VEC1' and 'VEC2,' each with a maximum size of N or M. As a result, the space complexity is O(N + M).
Frequently Asked Questions
What is Backtracking?
Backtracking is a form of Recursion in which we store the previous state of the program execution so that we may be able to utilize it again with different parameters.
What is a Binary Tree?
A Binary Tree is a type of Tree Data Structure where each node has a maximum of two children.
Conclusion
Solving questions like these teaches you computer science concepts and approaches to complex problems. We've got tons of such problems and blogs on the Coding Ninjas Platform. Also, recently Coding Ninjas has released a specially designed test series for acing Interviews- Coding Ninjas Studio Test Series.
Check out this problem - Root To Leaf Path
Recommended Reading:
Thanks for reading. I hope you’ve gained a lot from this blog.