C++ program to find mirror of a given node in binary tree














































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:
#include<bits/stdc++.h> 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.



More Articles of GHANASHYAM KATTI:

Name Views Likes
C++ std::reverse with std::vector 658 24
C++ std::search with std::vector 613 15
C++ std::is_permutation with std::vector 664 20
C++ program to reverse a path in binary search tree using queue 695 17
C++ std::partial_sort with std::vector 609 23
C++ std::partition_point with vector 631 15
C++ std::partition_point with multiset 704 27
C++ program to calculate tilt of binary tree 507 16
C++ program to find right sibling of a binary tree with parent pointers 936 16
C++ program to find root of the tree where children id sum for every node is given 665 21
C++ std::count with std::vector 673 23
C++ std::mismatch with std::deque 605 26
C++ std::partial_sort with std::array 758 12
C++ program to remove nodes on root to leaf paths of length < k 521 20
C++ std::mismatch with std::array 950 15
C++ std::is_permutation with std::array 570 14
C++ std::nth_element with std::array 786 23
C++ std::count_if with std::list 687 15
C++ std::move_backward with std::deque 636 12
C++ std::mismatch with std::list 576 19
C++ std::move_backward with std::list 698 20
C++ std::random_shuffle with std::array 564 24
C++ std::mismatch with std::forward_list 552 19
C++ std::count with std::array 772 26
C++ program to find simple recursive solution to check whether binary search tree contains dead end 728 19
C++ program to find ways to color a skewed tree such that parent and child have different colors 681 28
C++ std::count_if with std::array 786 23
C++ program to find deepest left leaf node in a binary tree using recursion 456 20
C++ program to check if a given binary tree is sumtree 546 11
C++ program to calculate size of a tree using recursion 760 11
C++ program to transform a binary search tree to greater sum tree 493 14
C++ program to find longest path with same values in a binary tree 965 11
C++ program to find extract leaves of a binary tree in a doubly linked list 514 17
C++ program to find sum of nodes at k-th level in a tree represented as string 839 16
C++ std::count_if with std::multiset 740 17
C++ std::count with std::deque 1572 20
C++ program to find all duplicate subtrees 690 15
C++ program to find mirror of a given node in binary tree 604 26
C++ program to find deepest right leaf node in a binary tree using recursion 549 17
C++ std::mismatch with std::vector 626 19
C++ program to find maximum width of a binary tree 637 14
C++ std::partition_point with std::array 595 16
C++ program to find distance from root to given node in a binary tree 510 14
C++ program to find factor tree of a given number 1171 16
C++ std::partition_point with std::list 803 13
C++ std::reverse with std::deque 896 21
C++ program to remove all nodes which don%u2019t lie in any path with sum>= k 593 17
C++ std::count with std::list 559 11
C++ std::partition_point with std::deque 662 20
C++ std::count_if with std::deque 674 26
C++ std::partial_sort with std::deque 683 13
C++ std::mismatch with std::multiset 656 21
C++ std::search with std::deque 581 20
C++ std::partition_point with std::forward_list 578 14
C++ std::count_if with std::vector 811 16
C++ program to find largest subtree having identical left and right subtrees 546 14
C++ std::random_shuffle with std::deque 1099 15
C++ std::nth_element with std::vector 630 19
C++ std::move_backward with std::array 724 20
C++ program to find a number in minimum steps 597 23
C++ std::reverse with std::array 724 18
C++ std::random_shuffle with std::vector 632 14
C++ program to check if all leaves are at same level 490 15
C++ std::count with std::multiset 449 14
C++ program to connect nodes at same level 523 21
C++ std::move_backward with std::vector 658 20
C++ std::is_permutation with std::deque 530 13
C++ std::search with std::array 685 17
C++ std::nth_element with std::deque 1219 18
C++ program to find longest consecutive sequence in binary tree 565 11

Comments