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

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output 

960 480 240 192 320 120 

Complexity Analysis

Time Complexity: 

The Time Complexity is O(N)

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

Space Complexity: 

The Space Complexity is 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).

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

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.

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.

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.

Conclusion

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.

Recommended Reading:

• Memory Hierarchy
• Creating a Binary Tree From Inorder and and Level Order Traversal
• Check if All the Nodes in a Binary Tree Having Common Values are at least D Distance Apart
• Find K Smallest Leaf Nodes From a Given Binary Tree
• How to Remove Subtrees Containing Zeros in Binary Trees
• Find Maximum GCD Value From Root To Leaf in a Binary Tree

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

Happy Coding!