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 Algorithm 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;
}
You can also try this code with Online C++ Compiler
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));
}
}
You can also try this code with Online Java Compiler
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))
You can also try this code with Online Python Compiler
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: We Store the depth of each node in a map with the node address as the key spece required is O(1).
Check out this problem - Diameter Of Binary Tree
Frequently Asked Questions
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.
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.
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.
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.
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.
Recommended Reading:
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.
Happy Coding!
85+ registered 