Covered / Uncovered Nodes

Asked in:
Amazon

Problem Description

You are given the root of a binary tree A, you need to return the absolute difference between sum of all covered elements and the sum of all uncovered elements.

In a binary tree, a node is called Uncovered if it appears either on left boundary or right boundary. Rest of the nodes are called covered.

Problem Constraints

1 <= Number of nodes in the binary tree <= 10⁵

Input Format

The first argument is the root of the binary tree A.

Output Format

Return a single integer denoting the absolute difference of the sum of covered and uncovered nodes.

Example Input

Input 1:

Input 2:

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1:

The node with value 10 is the only covered node. All other nodes are uncovered.
Therefore, the absolute difference is |(10) - (2 + 1 + 4 + 6 + 5)| = 8

Explanation 2:

All the given nodes are uncovered. Hence, the answer is sum of given nodes - 6.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Covered / Uncovered Nodes on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Asked In:

Amazon

Covered / Uncovered Nodes

Discussion