Minimize the sum of node values by filling a given empty Tree such that each node is GCD of its children

Amarjeet Kumar
Last Updated: May 12, 2022
Difficulty Level :
EASY

Introduction

In this article we'll look at a problem using Binary Trees to solve it. Binary Trees contain a lot of intriguing qualities, and we'll learn about them in this blog. Binary tree problems are common in coding interviews and programming competitions. The number of nodes in a complete binary tree can be counted in a variety of ways, as discussed in this article.

A tree is made up of nodes, which are individual things. Edges link nodes together. Each node has a value or piece of data and may or may not have a child node. The root refers to the tree's first node. Let’s start with the problem statement.

Problem Statement

The aim is to calculate the minimum sum of all the node's values of the given Tree such that the value of each node must equal the value of GCDs of its children, given a Binary Tree consisting of N nodes with no values and an integer X that represents the value of the root node. Aside from that, no two siblings can have the same worth.

GCD Concept

The greatest common divisor (GCD) of two or more numbers is the exact divisor number that divides them. It's also known as the greatest common factor (HCF). Because both integers can be divided by 5, the largest common factor of 15 and 10 is 5.

The greatest common factor of two or more numbers is called GCD. A factor number that is the highest among the others.
 

Input 

 

Output

Input

Output

Approach

Both of the offspring can have the value of X and 2*X, where X is the parent's value, to minimize the total. If a node only has one child, its value will be the same as its parent node. The depth of each subtree for each node will be examined to determine which child should have a value of X and 2*X to obtain the least total. The kid with the most depth will be assigned a value of X so that it can be transferred to more of its offspring, while another will be assigned a value of 2*X.  

  • Find each node's depth and save it in a map using the node's address as the key.
     
  • Now, beginning from the root node, conduct the DFS Traversal, assigning a value of X to each node that has a higher depth than its sibling in each call. In every other case, use the number 2*X.
     
  • Find the sum of both left and right child values while backtracking and return the entire sum, i.e. the sum of the left child, right child, and current node values in each call, after the previous step.
     
  • Print the result returned from the DFS Call as the smallest sum feasible after completing the preceding steps.

C++ implementation

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

class Node {
public:
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
class Tree {
public:
    unordered_map<Node*, int> depth;
 

    int findDepth(Node* current_data)
    {
        int max_start = 0;
        if (current_data->left) {
            max_start = findDepth(current_data->left);
        }
        if (current_data->right) {
            max_start = max(max_start, findDepth(current_data->right));
        }
 
    
        return depth[current_data] = max_start + 1;
    }
 
 
    int dfs(Node* current_data, bool flag, int parValue)
    {
        if (parValue != -1) {
            if (flag)
                current_data->data = parValue;
            else
                current_data->data = parValue * 2;
        }
        int l = 0, r = 0;
        if (current_data->left && current_data->right) {
            if (depth[current_data->left] > depth[current_data->right]) {
                l = dfs(current_data->left, 1, current_data->data
                r = dfs(current_data->right, 0, current_data->data);
            }
            else {
                l = dfs(current_data->left, 0, current_data->data);
                r = dfs(current_data->right, 1, current_data->data);
            }
        }
        else if (current_data->left) {
            l = dfs(current_data->left, 1, current_data->data);
        }
        else if (current_data->right) {
            r = dfs(current_data->right, 1, current_data->data);
        }
 
        return l + r + current_data->data;
    }
 

    int minimumSum(Node* root)
    {
  
        findDepth(root);
 
  
        return dfs(root, 1, -1);
    }
};
 

int main()
{
 

    int X = 2;
 

    Node* root = new Node(X);
    root->left = new Node(-1);
    root->right = new Node(-1);
    root->left->left = new Node(-1);
    root->left->right = new Node(-1);
    root->left->right->left = new Node(-1);
    root->left->right->right = new Node(-1);
    root->left->right->right->left = new Node(-1);
 
    Tree t;
 

    cout << t.minimumSum(root);
 
    return 0;
}

Output

22

Java implementation 

import java.util.*;
public class Main
{
    static class Node {   
        public int data;
        public Node left, right;
        
        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }
    }
    
    static HashMap<Node, Integer> depth = new HashMap<>();
    
    static int findDepth(Node current_data)
    {
        int max_data = 0;
        if (current_data.left != null) {
            max_data = findDepth(current_data.left);
        }
        if (current_data.right != null) {
            max_data = Math.max(max_data, findDepth(current_data.right));
        }
    
      
        depth.put(current_data, max_data + 1);
        return depth.get(current_data);
    }
    static int dfs(Node current_data, int flag, int parValue)
    {
        if (parValue != -1) {
            if (flag == 1)
                current_data.data = parValue;
            else
                current_data.data = parValue * 2;
        }
        int l = 0, r = 0;
        if (current_data.left != null && current_data.right != null) {
            if (depth.containsKey(current_data.left) && depth.containsKey(current_data.right) && depth.get(current_data.left) > depth.get(current_data.right)) {
                l = dfs(current_data.left, 1, current_data.data);
                r = dfs(current_data.right, 0, current_data.data);
            }
            else {
                l = dfs(current_data.left, 0, current_data.data);
                r = dfs(current_data.right, 1, current_data.data);
            }
        }
        else if (current_data.left != null) {
            l = dfs(current_data.left, 1, current_data.data);
        }
        else if (current_data.right != null) {
            r = dfs(current_data.right, 1, current_data.data);
        }
    
        return (l + r + current_data.data);
    }

    static int minimumSum(Node root)
    {  
        findDepth(root);
    
      
        return dfs(root, 1, -1);
    }
 
    public static void main(String[] args)
    {
 
        int X = 2;
  
        Node root = new Node(X);
        root.left = new Node(-1);
        root.right = new Node(-1);
        root.left.left = new Node(-1);
        root.left.right = new Node(-1);
        root.left.right.left = new Node(-1);
        root.left.right.right = new Node(-1);
        root.left.right.right.left = new Node(-1);
        
    
        System.out.print(minimumSum(root));
    }
}

Output

22

Python implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
depth = {}

def findDepth(current_data):
    mx = 0
    if (current_data.left != None):
        mx = findDepth(current_data.left)
    if (current_data.right != None):
        mx = max(mx, findDepth(current_data.right))

    depth[current_data] = mx + 1
    return depth[current_data]
 
def dfs(current_data, flag, parValue):
    if (parValue != -1):
        if flag:
          current_data.data = parValue
        else:
            current_data.data = parValue * 2
    l, r = 0,  0;
    if (current_data.left != None and current_data.right != None):
        if ((current_data.left in depth) and (current_data.right in depth) and depth[current_data.left] > depth[current_data.right]):
            l = dfs(current_data.left, 1, current_data.data)
            r = dfs(current_data.right, 0,current_data.data)
        else:
            l = dfs(current_data.left, 0, current_data.data)
            r = dfs(current_data.right, 1, current_data.data)
    elif (current_data.left != None):
        l = dfs(current_data.left, 1, current_data.data)
    elif (current_data.right != None):
        r = dfs(current_data.right, 1, current_data.data)
 
    return (l + r + current_data.data)
 
def minimumSum(root):
  
    findDepth(root)
 
    return dfs(root, 1, -1)
 
X = 2
 
root = Node(X)
root.left = Node(-1)
root.right = Node(-1)
root.left.left = Node(-1)
root.left.right =Node(-1)
root.left.right.left = Node(-1)
root.left.right.right = Node(-1)
root.left.right.right.left = Node(-1);
 
print(minimumSum(root))

Output

22

Complexities

Time complexity: O(n)

Reason: As we perform the DFS Traversal, starting with the root node, and add a value of X to each node that has more depth than its sibling in each call. So the complexity is O(n).

Auxiliary Space: O(1) 

Reason: As we Store the depth of each node in a map with the node address as the key spece required is O(1).

Frequently Asked Questions

  1. In a tree, what is a node?
    A tree is made up of nodes, which are individual things. Edges link nodes together. Each node has a value or piece of data and may or may not have a child node. The root is the tree's very first node. 
     
  2. What is tree programming?
    A tree is a type of hierarchical data structure that is made up of nodes. Value is represented by nodes, which are connected by edges.  The root node is the only node in the tree. This is where the tree comes from, so it doesn't have any parents.
     
  3. What is DFS in the graph?
    The depth-first search (DFS) technique is used to traverse or explore data structures such as trees and graphs. The algorithm starts from the root node (in the case of a graph, any random node can be used as the root node) and examines each branch as far as feasible before retracing.
     
  4. What is the node's degree in a tree?
    The degree of a node is defined as the total number of subtrees associated to that node. A leaf node's degree must be zero. The maximum degree of a node among all the nodes in the tree is the tree's degree.
     
  5. Is it possible for a tree node to have two parents?
    Yes, you may have "children" and "parents" in the same node. Because the graph is no longer tree-structured, you won't be able to utilize a TreeModel; instead, you'll need to use a GraphLinksModel.

Conclusion

In this article, we have solved a binary tree problem. Where we have to fill the provided empty Tree with nodes that are GCD of their offspring to minimize the total of node values. Want to explore more related to this topic click here.
If you want to learn more attempt our Online Mock Test Series on CodeStudio now!

Happy Coding!

Was this article helpful ?
0 upvotes