Executable on C++11/14/17
Description and Approach:
A template based program can be implemented here. The approach here is to travel on the outer most edges on both sides simultaneously, searching for the required target value. If not found, then move in for the internal nodes and apply the same mechanism until the required node is encountered.
Example:
In the above example:
* Node P is the mirror of node D.
* Node F has no mirror node.
* Node A being the root node is the mirror node of itself.
Implementation:
#include<bits/stdc++.h>
using namespace std;
template <typename T>
struct bin_node
{
T val;
bin_node<T> *l_child;
bin_node<T> *r_child;
};
template <typename T>
bin_node<T>* get_node(T val)
{
bin_node<T> *new_node = new bin_node<T>;
new_node->val = val;
new_node->l_child = NULL;
new_node->r_child = NULL;
return new_node;
}
template<typename T>
T mirror(T required, bin_node<T> *left_view, bin_node<T> *right_view)
{
if(!left_view || !right_view) //when a NULL node is encountered on any one of the sides, No need to proceed further
return T(0);
if( left_view->val == required ) //If the required value is on the left side, corresponding right mirror node is returned
return right_view->val;
if( right_view->val == required ) //Similar to above, but here corresponding left node is returned
return left_view->val;
T mirror_exist = mirror(required, left_view->l_child, right_view->r_child);
if(mirror_exist != T(0))
return mirror_exist;
return mirror(required, left_view->r_child, right_view->l_child);
}
int main()
{
bin_node<char> *root_node = get_node('A');
root_node->l_child = get_node<char>('Q');
root_node->r_child = get_node<char>('C');
root_node->l_child->l_child = get_node<char>('D');
root_node->l_child->r_child = get_node<char>('F');
root_node->l_child->l_child->l_child = get_node<char>('B');
root_node->r_child->r_child = get_node<char>('P');
root_node->r_child->r_child->l_child = get_node<char>('E');
char reqd_val, mirror_val = '\0';
cout<<"Enter the value whose mirror is required : "<<endl;
cin>>reqd_val;
if(root_node->val == reqd_val)
{
cout<<"Mirror of root node is always itself : "<<reqd_val<<endl;
return 0;
}
else
mirror_val = mirror(reqd_val, root_node->l_child, root_node->r_child);
if(mirror_val)
cout<<"The mirror of the required value is : "<<mirror_val<<endl;
else
cout<<"Mirror for the required value does not exist."<<endl;
return 0;
}
Time Complexity: O(n), We are just traversing through all the nodes in the tree.
Sample Output:
gs_katti@gsk-47534B:~/Desktop/CppSecret$ g++ 19.mirror_node.cpp
gs_katti@gsk-47534B:~/Desktop/CppSecret$ ./a.out
Enter the value whose mirror is required :
D
The mirror of the required value is : P
gs_katti@gsk-47534B:~/Desktop/CppSecret$ ./a.out
Enter the value whose mirror is required :
F
Mirror for the required value does not exist.
Comments