C++ program to find mirror of a given node in binary tree
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:
using namespace std;
//Structure of a node
template <typename T>
struct bin_node
{
T val;
bin_node<T> *l_child;
bin_node<T> *r_child;
};
//Function to get a new node
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;
}
//Function to find the mirror of the given 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); //Traverse through the left and right outer edges first
if(mirror_exist != T(0))
return mirror_exist;
return mirror(required, left_view->r_child, right_view->l_child); //If not found above, traverse through the internal nodes
}
//Driver program
int main()
{
bin_node<char> *root_node = get_node('A'); //root node initialisation
//constructing a sample binary tree
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