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.2.
Sample Examples
2.
Dynamic Programming Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What are the basics of dynamic programming?
3.2.
What is the time complexity of dynamic programming?
3.3.
Why is dynamic programming better than brute force?
4.
Conclusion
Last Updated: Mar 27, 2024

Check Sum of Covered and Uncovered nodes of Binary Tree

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In a binary tree, there can be two kinds of nodes. The nodes at the border of the tree, either left or right, are called the uncovered nodes. The rest of the nodes inside the binary tree’s borders are called covered nodes.

Source

Let’s discuss how to check the sum of the covered nodes and the uncovered nodes of a given binary tree.

Problem Statement

In this problem, we have to check the sum of the covered nodes and the uncovered nodes of a given binary tree.

Sample Examples

Input: The given binary tree is

             2

           /    \

        3        6

       /  \       /  \

     1   12   5   5

Output: The sum of the covered and uncovered nodes in the given binary tree is the same.

Explanation: The sum of the covered nodes (12 + 5 = 17) and the sum of the uncovered nodes (2 + 3 + 6 + 1 + 5 = 17) is the same.

Dynamic Programming Approach

In this approach, we use dynamic programming to optimize our code. First, we calculate the sum of all the nodes in the binary tree. Then to get the left bordering nodes, we start at the root and keep going to the left subtrees. In case there is no left tree, we take the right subtree since that will be the left bordering subtree. We keep doing this until we reach a leaf node. The sum of the values traversed is the sum of the left bordering nodes. We repeat the process for the right bordering nodes by traversing the right subtrees. The sum of both these traversals is the sum of the uncovered nodes. Subtract this value from the total sum to get the sum of the covered nodes.

Source

Algorithm

  1. First, we get the sum of all the nodes in the binary tree by recursively taking a node and adding its value to its child nodes and then moving on to the child nodes to do the same.
  2. Then we get the sum of the uncovered nodes by dividing the function into two different functions: the sum of the left bordering nodes function (uncLSum) and the sum of the right bordering nodes function (uncRSum).
  3. In case the root node has a left subtree, we move to the uncLSum function to find the sum of this subtree. Here, there are three possible cases:
    1. The root’s left child node is a leaf node. So the sum of the left subtree is the value of the left child node.
    2. If the root’s left child node has a left child node of its own, we can recursively run the same uncLSum function to find the value of that subtree. Adding that value to the left child node’s value would give the sum for the original left subtree.
    3. If the root’s left child node has no left child node of its own, we move to its right child and run the uncRSum function. The uncRSum function is almost the same, except it traverses the right subtrees to get the sum.
  4. Then, in case the root node has a right subtree, we move to uncRSum function to find the sum of this subtree. This process is exactly like step 3, except that the function traverses the right child instead of the left.
  5. Now that we have the value of both the left and the right uncovered nodes, we can add them to get the total sum of the uncovered nodes. Subtracting this from the sum of all the nodes in the binary tree would get us the sum of the covered nodes.

Implementation in C++

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

struct Node {
    int key;
    struct Node* left, *right;
};

struct Node* newNode(int key) {
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return(temp);
}

int sum(Node* t) {
    if(t == NULL)
        return 0;
    return t->key + sum(t->left) + sum(t->right);
}

int uncLSum(Node* t) {
    if(t->left == NULL && t->right == NULL)
        return t->key;

    if(t->left != NULL)
        return t->key + uncLSum(t->left);
    else
        return t->key + uncLSum(t->right);
}

int uncRSum(Node* t) {
    if(t->left == NULL && t->right == NULL)
        return t->key;

    if(t->right != NULL)
        return t->key + uncRSum(t->right);
    else
        return t->key + uncRSum(t->left);
}

int uncSum(Node* t) {
    int lb = 0, rb = 0;
 
    if(t->left != NULL)
        lb = uncLSum(t->left);
    if(t->right != NULL)
        rb = uncRSum(t->right);

    return t->key + lb + rb;
}

bool SameSum(Node *root) {
    int sumUC = uncSum(root);
    int sumT = sum(root);
    return (sumUC == (sumT - sumUC));
}

int main() {
    Node* root = newNode(2);
    root->left = newNode(3);
    root->left->left = newNode(1);
    root->left->right = newNode(12);
    root->right = newNode(6);
    root->right->right = newNode(5);
    root->right->left = newNode(5);

    if (SameSum(root))
        printf("Sum of covered and uncovered nodes are the same\n");
    else
        printf("Sum of covered and uncovered nodes are not the same\n");
}

 

Output:

Sum of covered and uncovered nodes are the same

 

Complexity Analysis

Time Complexity: O(N)

Explanation: The code will run for every new node, so the time complexity is O(N).

Space Complexity: O(N)

Explanation: In this approach, space is needed for every node, so the space complexity is O(N).

Check out this problem - Two Sum Problem

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 are the basics of dynamic programming?

Dynamic programming is a problem-solving approach that divides issues into sub-problems and stores the answer for later use, eliminating the need to recalculate the result. The optimum substructure property describes how subproblems are improved to improve the overall solution.

What is the time complexity of dynamic programming?

Time complexity in dynamic programming issues is defined as the number of distinct states/subproblems multiplied by the time spent on each state. Say there are n unique states/subproblems in any given issue for a given n. Each state is supposed to be solved in a constant time for the sake of convenience. As a result, the time complexity is O(n * 1).

Why is dynamic programming better than brute force?

Using dynamic programming instead of brute force is substantially faster. Dynamic programming is often linear in its time complexity, while brute force can take an exponential amount of time.

Conclusion

In conclusion, we discussed different approaches to check the sum of the covered nodes and the uncovered nodes of a given binary tree. For every approach, we discussed algorithms and complexities. We eventually saw how each of the methods are different from the others.

 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Maximum Level Sum in Binary Tree
Next article
Print Cousins of A Given Node in a Binary Tree
Live masterclass