Modify Binary Tree By Replacing Each Node With The Product Of All Remaining Nodes

Rhythm Jain
Last Updated: May 13, 2022

Introduction

A binary tree is a tree data structure in which each node has a maximum of two children, known as the left and right children.

Binary tree problems are frequently asked in many programming interviews, so it is crucial to have a nice grab on binary trees and related questions.

Today we will encounter one such problem.

Problem Statement

We have a binary tree with N nodes. Our task is to modify the tree such that each node is replaced by the product of all the remaining nodes of the tree.

Example:

Assume we have the following tree as input:

 

                    1

                  /  \

               2    3

             / \      \

          4   5      8

 

Output:

                  960

                  /    \

             480    320

             /    \         \

          240   192    120

Approach

The above problem may be handled by first computing the product of all nodes in the provided Tree, then traversing the tree and updating each node.

Algorithm:

  • Using any traversal (say preorder), calculate the product “Pr” of all the nodes.
  • Traverse the tree using any technique (say preorder) and update root value as root value=(Pr/ root value), and call the function recursively for its left and right subtrees.
  • If the root is NULL, return NULL.
  • Print the tree.(preorder traversal)

Code

#include <bits/stdc++.h>
using namespace std;


class TreeNode {
    public:
int data;
TreeNode* left;
TreeNode* right;

TreeNode (int x){
    data=x;
    left=NULL;
    right=NULL;
}
};


int calcProduct(TreeNode* root){
    if(root==nullptr) return 1;
    int left=calcProduct(root->left);
    int right=calcProduct(root->right);
    return (root->data)*left*right;
}
TreeNode* treeProduct(TreeNode* root,int Pr){
    if(root==NULL) return NULL;
    root->data=(Pr/(root->data));
    root->left=treeProduct(root->left,Pr);
    root->right=treeProduct(root->right,Pr);
    return root;
    
}
void printTree(TreeNode* root){
    if(root==nullptr) return;
    cout<<root->data<<" ";
    printTree(root->left);
    printTree(root->right);
}
int main()
{
/*
    Constructed binary tree is:
          1
        /  \
       2    3
     /  \    \
    4   5     8


     */
    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);
    root1->left->left = new TreeNode(4);
    root1->left->right = new TreeNode(5);
    root1->right->right = new TreeNode(8);
    
    int Pr=calcProduct(root1);
    root1=treeProduct(root1,Pr);
    printTree(root1);


return 0;
}

 

Output 

960 480 240 192 320 120 

Complexity Analysis

Time Complexity: O(N)

Where N is the number of nodes in the tree, because we are traversing the whole tree while calling recursively for both left and right subtree, So we need to visit each node in the tree.

Space Complexity: O(H)

Where H=height of the given binary tree

Since we are recursively calling for left and right subtree, the stack memory space for recursion is O(H). In the worst case, i.e. when the binary tree is skewed, then its height is equal to the number of nodes, so in that case, the time complexity becomes O(n).

Frequently Asked Questions

  1. What is a Binary Tree?
    A binary tree is a non-linear data structure of the tree type, with a maximum of two offspring for each parent. Every node in a binary tree has a left and right reference and the data element. The root node is at the top of a tree's hierarchy.
     
  2. What is a self-balanced binary tree?
    When insertion and deletion operations are performed, self-balanced binary search trees retain their height as minimal as possible.
     
  3. What is the height of a complete binary tree with total N nodes?
    For a complete binary tree, the height is ceil(Log(N+1)-1) which is approximately O(log N). That is why most binary tree operations are O(log N) in nature.

Key Takeaways

Today we solved a fundamental problem on binary search trees. To improve your basics, look at the examples presented in this article and practice altering values.

Want to know more about various kinds of tree traversals? Click here.

If you want to master Binary Search Trees, look at Binary Search Tree.

If you wish to practice more Tree related problems, you can visit TOP TREES INTERVIEW QUESTIONS.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think