Given a complete binary tree, the task is to find the sum of mirror image nodes in an inorder way i.e. find the inorder traversal of the left sub-tree and for every node traversed, add the value of its mirror node to the current node’s value.
Examples:
Input:
Output:
20
51
19
10
Inorder traversal of the left sub-tree of the given tree is 4 23 11 5.
Adding the mirror nodes,
4 + 16 = 20
23 + 28 = 51
11 + 8 = 19
5 + 5 = 10
Approach: We will use 2 pointers to maintain 2 nodes which are the mirror image of each other. So let’s take root1 and root2 are 2 mirror image nodes. Now left child of root1 and right child of root2 will be the mirror image of each other. We will pass these two nodes (root1->left and root2->right) for next recursive call. Since we have to traverse in an inorder manner so once left sub-tree is traversed then we print the current root data and then we traverse the right sub-tree. Similarly for the right sub-tree so right child of root1 and left child of root2 will be the mirror image of each other. We will pass these two nodes (root1->right and root2->left) for next recursive call.
Below is the implementation of the above approach
C++
// C++ implementation of the approach#include <iostream>using namespace std;typedef struct node { // struct to store data and links to // its left and right child int data; struct node* l; struct node* r; node(int d) { // Initialize data for the current node // with the passed value as d data = d; // Initialize left child to NULL l = NULL; // Initialize right child to NULL r = NULL; }} Node;// Function to print the required inorder traversalvoid printInorder(Node* rootL, Node* rootR){ // We are using 2 pointers for the nodes // which are mirror image of each other // If both child are NULL return if (rootL->l == NULL && rootR->r == NULL) return; // Since inorder traversal is required // First left, then root and then right printInorder(rootL->l, rootR->r); cout << rootL->l->data + rootR->r->data << endl; printInorder(rootL->r, rootR->l);}// Driver codeint main(){ Node* root = new Node(5); root->l = new Node(23); root->r = new Node(28); root->l->l = new Node(4); root->l->r = new Node(11); root->r->l = new Node(8); root->r->r = new Node(16); printInorder(root, root); // Since root is mirror image of itself if (root) cout << root->data * 2 << endl; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ static class Node { // struct to store data and links to // its left and right child int data; Node l; Node r; Node(int d) { // Initialize data for the current Node // with the passed value as d data = d; // Initialize left child to null l = null; // Initialize right child to null r = null; } } // Function to print the required inorder traversal static void printInorder(Node rootL, Node rootR) { // We are using 2 pointers for the Nodes // which are mirror image of each other // If both child are null return if (rootL.l == null && rootR.r == null) return; // Since inorder traversal is required // First left, then root and then right printInorder(rootL.l, rootR.r); System.out.println(rootL.l.data + rootR.r.data ); printInorder(rootL.r, rootR.l); } // Driver code public static void main(String args[]) { Node root = new Node(5); root.l = new Node(23); root.r = new Node(28); root.l.l = new Node(4); root.l.r = new Node(11); root.r.l = new Node(8); root.r.r = new Node(16); printInorder(root, root); // Since root is mirror image of itself if (root != null) System.out.println(root.data * 2 ); }}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach class Node: def __init__(self, d): self.data = d self.l = None self.r = None# Function to print the required inorder traversal def printInorder(rootL, rootR): # We are using 2 pointers for the nodes # which are mirror image of each other # If both child are None return if rootL.l == None and rootR.r == None: return # Since inorder traversal is required # First left, then root and then right printInorder(rootL.l, rootR.r) print(rootL.l.data + rootR.r.data) printInorder(rootL.r, rootR.l) # Driver code if __name__ == "__main__": root = Node(5) root.l = Node(23) root.r = Node(28) root.l.l = Node(4) root.l.r = Node(11) root.r.l = Node(8) root.r.r = Node(16) printInorder(root, root) # Since root is mirror image of itself if root: print(root.data * 2) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System;class GFG{ public class Node { // struct to store data and links to // its left and right child public int data; public Node l; public Node r; public Node(int d) { // Initialize data for the current Node // with the passed value as d data = d; // Initialize left child to null l = null; // Initialize right child to null r = null; } } // Function to print the required inorder traversal static void printInorder(Node rootL, Node rootR) { // We are using 2 pointers for the Nodes // which are mirror image of each other // If both child are null return if (rootL.l == null && rootR.r == null) return; // Since inorder traversal is required // First left, then root and then right printInorder(rootL.l, rootR.r); Console.WriteLine(rootL.l.data + rootR.r.data ); printInorder(rootL.r, rootR.l); } // Driver code public static void Main(String []args) { Node root = new Node(5); root.l = new Node(23); root.r = new Node(28); root.l.l = new Node(4); root.l.r = new Node(11); root.r.l = new Node(8); root.r.r = new Node(16); printInorder(root, root); // Since root is mirror image of itself if (root != null) Console.WriteLine(root.data * 2 ); }}// This code is contributed by Arnab Kundu |
Javascript
<script>// Javascript implementation of the approachclass Node{ constructor(d) { this.l = null; this.r = null; this.data = d; }}// Function to print the required inorder traversalfunction printInorder(rootL, rootR){ // We are using 2 pointers for the Nodes // which are mirror image of each other // If both child are null return if (rootL.l == null && rootR.r == null) return; // Since inorder traversal is required // First left, then root and then right printInorder(rootL.l, rootR.r); document.write(rootL.l.data + rootR.r.data + "</br>"); printInorder(rootL.r, rootR.l);}// Driver codelet root = new Node(5);root.l = new Node(23);root.r = new Node(28);root.l.l = new Node(4);root.l.r = new Node(11);root.r.l = new Node(8);root.r.r = new Node(16);printInorder(root, root);// Since root is mirror image of itselfif (root != null) document.write(root.data * 2 );// This code is contributed by suresh07</script> |
Output:
20 51 19 10
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
