Given a Binary Tree, the task is to convert the given Binary Tree to the Symmetric Tree by adding the minimum number of nodes in the given Tree.
Examples:
Input:
Output:
Input:
Output:
Approach: To solve this problem, follow the below steps:
- Make a function buildSymmetricTree which will accept two parameters root1 and root2.
- Here, root1 and root2, are the nodes that are at the symmetrical places of one another.
- So initially, both root1 and root2 will contain the value of the root and in each recursive call:
- If root1 exists but root2 doesn’t then create a new node with the value same as root1 and place it in the position of root2.
- Follow the above step also for root1 if root2 exists but root1 doesn’t.
- If the value of root1 and root2 is not the same, then change the value of both nodes to the sum of them.
- Now, make the next two recursive calls for the symmetrical positions at (root1->left, root2->right) and (root1->right, root2->left).
- The tree will become symmetrical after all recursive calls will be made.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Node class Node { public : int val; Node *left, *right; Node( int val) { this ->val = val; left = right = NULL; } }; // Function to convert the given tree // into a symmetric Node* buidSymmetricTree(Node* root1, Node* root2) { // Base Case if (root1 == NULL and root2 == NULL) { return NULL; } // If root1 == NULL & root2 != NULL if (root1 == NULL) { // Create new node for root2 // and attaching it to tree Node* node = new Node(root2->val); root1 = node; } // If root2 == NULL and root1 != NULL if (root2 == NULL) { // Create new node for root1 // and attaching it to tree Node* node = new Node(root1->val); root2 = node; } // If both nodes are different // then change both nodes values // to the sum of them if (root1->val != root2->val) { int temp = root1->val + root2->val; root1->val = temp; root2->val = temp; } // Recurring to the left root1->left = buidSymmetricTree( root1->left, root2->right); // Recurring to the right root1->right = buidSymmetricTree( root1->right, root2->left); // Return root pointer return root1; } // Function to perform the Inorder // Traversal of the tree void inorder(Node* root) { // Base Case if (root == NULL) return ; inorder(root->left); cout << root->val << " " ; inorder(root->right); } // Driver Code int main() { Node* root = new Node(3); root->left = new Node(2); root->right = new Node(4); root->left->left = new Node(5); // Function to make the given // tree symmetric buidSymmetericTree(root, root); // Print the inorder traversal inorder(root); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Node static class Node { int val; Node left, right; Node( int val) { this .val = val; left = right = null ; } }; // Function to convert the given tree // into a symmetric static Node buidSymmetricTree(Node root1, Node root2) { // Base Case if (root1 == null && root2 == null ) { return null ; } // If root1 == null & root2 != null if (root1 == null ) { // Create new node for root2 // and attaching it to tree Node node = new Node(root2.val); root1 = node; } // If root2 == null and root1 != null if (root2 == null ) { // Create new node for root1 // and attaching it to tree Node node = new Node(root1.val); root2 = node; } // If both nodes are different // then change both nodes values // to the sum of them if (root1.val != root2.val) { int temp = root1.val + root2.val; root1.val = temp; root2.val = temp; } // Recurring to the left root1.left = buidSymmetricTree( root1.left, root2.right); // Recurring to the right root1.right = buidSymmetricTree( root1.right, root2.left); // Return root pointer return root1; } // Function to perform the Inorder // Traversal of the tree static void inorder(Node root) { // Base Case if (root == null ) return ; inorder(root.left); System.out.print(root.val+ " " ); inorder(root.right); } // Driver Code public static void main(String[] args) { Node root = new Node( 3 ); root.left = new Node( 2 ); root.right = new Node( 4 ); root.left.left = new Node( 5 ); // Function to make the given // tree symmetric buidSymmetericTree(root, root); // Print the inorder traversal inorder(root); } } // This code is contributed by umadevi9616 |
Python3
# Python Program to implement # the above approach # Node class Node: def __init__( self , val): self .val = val self .left = self .right = None # Function to convert the given tree # into a symmetric def buidSymmetricTree(root1, root2): # Base Case if (root1 = = None and root2 = = None ): return None # If root1 == null & root2 != null if (root1 = = None ): # Create new node for root2 # and attaching it to tree node = Node(root2.val) root1 = node # If root2 == null and root1 != null if (root2 = = None ): # Create new node for root1 # and attaching it to tree node = Node(root1.val) root2 = node # If both nodes are different # then change both nodes values # to the sum of them if (root1.val ! = root2.val): temp = root1.val + root2.val root1.val = temp root2.val = temp # Recurring to the left root1.left = buidSymmetricTree( root1.left, root2.right) # Recurring to the right root1.right = buidSymmetricTree(root1.right, root2.left) # Return root pointer return root1 # Function to perform the Inorder # Traversal of the tree def inorder(root): # Base Case if (root = = None ): return inorder(root.left) print (root.val, end = " " ) inorder(root.right) # Driver Code root = Node( 3 ) root.left = Node( 2 ) root.right = Node( 4 ) root.left.left = Node( 5 ) # Function to make the given # tree symmetric buidSymmetericTree(root, root) # Print the inorder traversal inorder(root) # This code is contributed by gfgking. |
C#
// C# program for the above approach using System; public class GFG { // Node public class Node { public int val; public Node left, right; public Node( int val) { this .val = val; left = right = null ; } }; // Function to convert the given tree // into a symmetric static Node buidSymmetricTree(Node root1, Node root2) { // Base Case if (root1 == null && root2 == null ) { return null ; } // If root1 == null & root2 != null if (root1 == null ) { // Create new node for root2 // and attaching it to tree Node node = new Node(root2.val); root1 = node; } // If root2 == null and root1 != null if (root2 == null ) { // Create new node for root1 // and attaching it to tree Node node = new Node(root1.val); root2 = node; } // If both nodes are different // then change both nodes values // to the sum of them if (root1.val != root2.val) { int temp = root1.val + root2.val; root1.val = temp; root2.val = temp; } // Recurring to the left root1.left = buidSymmetricTree(root1.left, root2.right); // Recurring to the right root1.right = buidSymmetricTree(root1.right, root2.left); // Return root pointer return root1; } // Function to perform the Inorder // Traversal of the tree static void inorder(Node root) { // Base Case if (root == null ) return ; inorder(root.left); Console.Write(root.val + " " ); inorder(root.right); } // Driver Code public static void Main(String[] args) { Node root = new Node(3); root.left = new Node(2); root.right = new Node(4); root.left.left = new Node(5); // Function to make the given // tree symmetric buidSymmetericTree(root, root); // Print the inorder traversal inorder(root); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript Program to implement // the above approach // Node class Node { constructor(val) { this .val = val; this .left = this .right = null ; } }; // Function to convert the given tree // into a symmetric function buidSymmetricTree(root1, root2) { // Base Case if (root1 == null && root2 == null ) { return null ; } // If root1 == null & root2 != null if (root1 == null ) { // Create new node for root2 // and attaching it to tree let node = new Node(root2.val); root1 = node; } // If root2 == null and root1 != null if (root2 == null ) { // Create new node for root1 // and attaching it to tree let node = new Node(root1.val); root2 = node; } // If both nodes are different // then change both nodes values // to the sum of them if (root1.val != root2.val) { let temp = root1.val + root2.val; root1.val = temp; root2.val = temp; } // Recurring to the left root1.left = buidSymmetricTree( root1.left, root2.right); // Recurring to the right root1.right = buidSymmetricTree( root1.right, root2.left); // Return root pointer return root1; } // Function to perform the Inorder // Traversal of the tree function inorder(root) { // Base Case if (root == null ) return ; inorder(root.left); document.write(root.val + " " ); inorder(root.right); } // Driver Code let root = new Node(3); root.left = new Node(2); root.right = new Node(4); root.left.left = new Node(5); // Function to make the given // tree symmetric buidSymmetericTree(root, root); // Print the inorder traversal inorder(root); // This code is contributed by Potta Lokesh </script> |
Output:
5 6 3 6 5
Time Complexity: O(N)
Auxiliary Space: O(1)
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!