Question:
Given a binary tree, get the difference of the sum of the nodes at odd level and sum of the nodes at even level.
Example:
Consider the image given below:
Form the image above,
The sum of nodes at odd level is 16 + 7 + 15 + 18 + 30 = 86
The sum of nodes at even level is 10 + 25 = 35
So the output should be 86 – 35 = 51
Solution:
This problem can be solved by recursive traversal.
Assume if you have only one node, and no left and right node.
Now, you will do
root – left_node – right_node
= 16 – 0 – 0 = 16
Suppose,
if you have left and right children as shown below:
root – left_node – right_node
= 16 – 10 – 25 = -19
We apply similar logic to all the nodes.
return root->data - get_level_diff(root->left) - get_level_diff(root->right);
We call “get_level_diff” recursively for left and right nodes, and arrive at the solution.
Recursion Visualization:
As we are calling the “get_level_diff” recursively, let us understand how it will work:
We take an empty stack, and stack will grow as follows:
So we perform similar recursive call to all the nodes and arrive at our solution.
Solution in C++
#include <iostream> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; int get_level_diff(Node *root) { // Base case if (root == NULL) return 0; return root->data - get_level_diff(root->left) - get_level_diff(root->right); } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); cout<<"Solution = " << get_level_diff(root)<<endl; return 0; }
Output:
Solution = 51