Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.1.1.
Sample Examples
2.
Solution Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the difference between a binary tree and a binary search tree?
3.2.
What is inorder traversal ? 
3.3.
Difference between a full binary tree and a complete binary tree? 
4.
Conclusion
Last Updated: Mar 27, 2024

Convert the Given binary Tree into a Symmetric Tree by adding a minimum number of nodes

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Binary trees are like salt to an interview,i.e., every tech interview is incomplete without binary trees. Thus to get an edge over our competition, it is very important to master binary trees. But when Ninja is here, you don’t have to go to any other place. Today we will be seeing one such important problem on Binary Trees, 

Also see, Data Structures

Problem Statement

The problem states that we need to convert the given binary tree into a symmetric Tree by adding a minimum number of nodes. If two nodes have different values opposite each other, then replace the value of both nodes with their sum. 

Let us recap what a binary tree is, and a symmetric tree is: 

Binary Tree:

As the name suggests, a binary tree is a tree in which every node can have at most two children, and they are known as the left and right children. 

Symmetric Tree:

The symmetric tree is a special type of tree, which is a mirror image of itself about the root node. When we divide the tree along with the root node, the two trees we will get will be identical. 

Sample Examples

Example 1:

Input: Given The binary Tree, convert it into a symmetric Tree. 

Binary Tree


Output

Binary Tree

ExplanationWe have added two nodes, i.e., a node with value 3 and value 4  in the left subtree of the root node, to make the given binary tree into a symmetric tree.

 

Example 2:

Input: Given The binary Tree, convert it into a symmetric Tree.

Binary Tree

Output

Binary Tree

Explanation

In the right subtree, we replace the node with the value 4 with 4 + 2(because the node with value 2 is at symmteric position with this node), which becomes 6. 

We replace the node with value 6 in the right subtree with value 5 + 6(because the node with value 5 is at symmetric position with this node), which becomes 11. . 

Solution Approach

The idea is simple, we travel the right and left subtree of the root and the nodes at symmetrical places to one another; we will check, and if any node does not exist, we will create and insert that node. If the value of nodes with symmetric places is not the same, we will replace the values of both nodes with the sum of both nodes. 

Steps of Algorithm

  1. Make a function convertSymmetric(), and it will accept two parameters, namely root1, and root2, root1, and root2 are the nodes at symmetrical places with respect to one another. 
  2. There can be 2 cases possible, either root1 or root2 does not exist, or the values of root1 and root2 are not the same. 
  3. If root2 exists and root1 does not exist, create a new node with a value the same as root2 and insert it at the position of root1 and vice-versa if root 1 exists and root2 does not exist.
  4. Now make recursive call for symmetric position to a function convertSymmetric(root1->left, root2->right) and convertSymmetric(root1->right, root->left). 
  5. The Binary tree will become a symmetric tree after all recursive calls is over.  

Implementation in C++

// C++ implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
// declaring the structure of the
// Tree Node
class TreeNode{
    public:
        TreeNode *left, *right;
        int data;
    TreeNode(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

// utility function to convert the given
// tree into the symmetric tree
TreeNode* convertSymmetric(TreeNode *root1, TreeNode *root2){
    // Base Case,
    // If both root1 and root2 are NULL
    if(!root1 && !root2){
        return NULL;
    }
    // if  root2 exist, but root1 is NULL
    if(!root1){
        TreeNode* newNode = new TreeNode(root2->data);
        root1 = newNode;
    }
    // if root1 exist, but root2 is NULL
    if(!root2){
        TreeNode *newNode = new TreeNode(root1->data);
        root2 = newNode;
    }
    // if both roo1 and root2 exist, but
    // their values are not same,
    // replace both the nodes
    // with their sum
    if(root2->data != root1->data){
        int sum = root1->data + root2->data;
        root1->data = sum;
        root2->data = sum;
    }
    // call the recursive function
    // call to the left
    root1->left = convertSymmetric(root1->left, root2->right);
    // calling to the right
    root1->right = convertSymmetric(root1->right, root2->left);
    return  root1;
}

void inorder(TreeNode *root){
    if(!root)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main(){
    // inserting the nodes into the tree
    TreeNode *root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->right = new TreeNode(4);
    root->right->right = new TreeNode(6);
    cout << "Inorder Traversal before  calling the function: ";
    inorder(root);
    root = convertSymmetric(root, root);
    cout << endl << "Inorder Traversal After calling the function: ";
    inorder(root);
}

 

Output: 

Inorder Traversal before calling the function: 5 2 3 4 6
Inorder Traversal After calling the function: 11 6 3 6 11

 

Complexity Analysis

Time Complexity: O(N)

Explanation: Since we are traversing the complete binary tree only once, hence its time complexity is O(N). 

Space ComplexityO(1)

Explanation: No extra space is used. 

Check out this problem - Mirror A Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the difference between a binary tree and a binary search tree?

A tree that has a maximum of 2 children is called a binary tree, whereas a binary search tree is a particular binary tree having the following properties. 

Keys in the left subtree are always smaller than the root’s node, whereas keys in the right subtree are greater than the root’s node. 

What is inorder traversal ? 

In inorder traversal, we first traverse the left subtree, then visit the root and then traverse the right subtree. 

Difference between a full binary tree and a complete binary tree? 

A full binary tree is a binary tree in which every node has either 0 or 2 children; no one can have one child, while a complete binary tree is a tree in which all levels are filled, except possibly the last level, which will start to fill from left to right. 

Conclusion

This article discusses the problem of converting the given binary tree into a symmetric tree by adding a minimum number of Nodes. We hope you understand the problem and solution properly. Now you can try the more similar questions.

Recommended Reading:

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Live masterclass