Check Sum of Covered and Uncovered nodes of Binary Tree

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

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

Run Code

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