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.


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.

#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::partition_point with std::list 412 13
C++ std::partition_point with std::forward_list 332 14
C++ std::partition_point with multiset 406 27
C++ std::partition_point with std::array 367 16
C++ std::partition_point with std::deque 349 20
C++ std::partition_point with vector 309 15
C++ std::move_backward with std::list 360 20
C++ std::move_backward with std::deque 343 12
C++ std::move_backward with std::vector 341 20
C++ std::move_backward with std::array 286 20
C++ std::mismatch with std::forward_list 309 19
C++ std::mismatch with std::multiset 372 21
C++ std::mismatch with std::list 321 19
C++ std::mismatch with std::deque 355 26
C++ std::mismatch with std::vector 303 19
C++ std::mismatch with std::array 422 15
C++ std::partial_sort with std::array 356 12
C++ std::partial_sort with std::deque 283 13
C++ std::partial_sort with std::vector 324 23
C++ std::is_permutation with std::array 264 14
C++ std::is_permutation with std::vector 282 20
C++ std::is_permutation with std::deque 269 13
C++ std::reverse with std::deque 291 21
C++ std::reverse with std::vector 317 24
C++ std::reverse with std::array 281 18
C++ std::random_shuffle with std::deque 283 15
C++ std::random_shuffle with std::vector 330 14
C++ std::random_shuffle with std::array 299 24
C++ std::search with std::array 325 17
C++ std::search with std::vector 294 15
C++ std::search with std::deque 341 20
C++ std::nth_element with std::deque 508 18
C++ std::nth_element with std::array 338 23
C++ std::nth_element with std::vector 296 19
C++ std::count_if with std::vector 403 16
C++ std::count_if with std::list 290 15
C++ std::count_if with std::deque 307 26
C++ std::count_if with std::multiset 262 17
C++ std::count_if with std::array 325 23
C++ std::count with std::array 381 26
C++ std::count with std::multiset 248 14
C++ std::count with std::deque 335 20
C++ std::count with std::list 269 11
C++ std::count with std::vector 331 23
C++ program to reverse a path in binary search tree using queue 317 17
C++ program to connect nodes at same level 297 21
C++ program to remove all nodes which don%u2019t lie in any path with sum>= k 327 17
C++ program to find ways to color a skewed tree such that parent and child have different colors 320 28
C++ program to find root of the tree where children id sum for every node is given 329 21
C++ program to find largest subtree having identical left and right subtrees 248 14
C++ program to find mirror of a given node in binary tree 325 26
C++ program to find longest path with same values in a binary tree 278 11
C++ program to remove nodes on root to leaf paths of length < k 275 20
C++ program to find a number in minimum steps 279 23
C++ program to find longest consecutive sequence in binary tree 288 11
C++ program to find all duplicate subtrees 281 15
C++ program to find right sibling of a binary tree with parent pointers 331 16
C++ program to find extract leaves of a binary tree in a doubly linked list 236 17
C++ program to check if a given binary tree is sumtree 217 11
C++ program to find simple recursive solution to check whether binary search tree contains dead end 332 19
C++ program to find factor tree of a given number 384 16
C++ program to calculate tilt of binary tree 227 16
C++ program to check if all leaves are at same level 213 15
C++ program to find distance from root to given node in a binary tree 191 14
C++ program to find maximum width of a binary tree 190 14
C++ program to find deepest right leaf node in a binary tree using recursion 194 17
C++ program to find deepest left leaf node in a binary tree using recursion 153 20
C++ program to calculate size of a tree using recursion 348 11
C++ program to transform a binary search tree to greater sum tree 219 14
C++ program to find sum of nodes at k-th level in a tree represented as string 207 16