SDE - Intern

Given a binary tree and the value of two nodes, find the distance between the given two nodes of the Binary Tree.

Distance between two nodes is defined as the minimum number of edges in the path from one node to another.

You are given a binary tree, in which the data present in the nodes are integers. You are also given an integer X.

Your task is to delete all the leaf nodes with value X. In the process, if the newly formed leaves also have value X, you have to delete them too.

For example:

For the given binary tree, and X = 3:

You are given a binary tree of 'N' nodes.

Your task is to find the path from the leaf node to the root node which has the maximum path sum among all the root to leaf paths.

For Example:

All the possible root to leaf paths are:
3, 4, -2, 4 with sum 9
5, 3, 4 with sum 12
6, 3, 4 with sum 13
Here, the maximum sum is 13. Thus, the output path will be 6, 3, 4.

Note:

There will be only 1 path with max sum.

Ninja owns an electronic shop. In the shop, Ninja has 'N' bulbs. To sell these bulbs, Ninja has to check if they are of good quality. To check bulbs, Ninja uses a unique technique.

In this technique, in the first round he, turn on all the bulbs, then in the second round, he turns off every second bulb then in the third round, he chooses every third bulb and turns off it is on, or turn on if it is off and so no. He repeats this process 'N' times.

The number of bulbs that are on after the end of 'N' rounds are of good quality. Your task is to help Ninja in finding the number of good bulbs.

Example

Let 'N' = 4

Then in the first round, all bulbs are on.

In the second round bulbs, 2 and 4 are turned off.

In the third round bulb, 3 is turned off.

In the fourth round bulb, 4 is turned on.

So at the end of 'N' (4) round, only the bulb 1 and 4 is on, so there are 2 good bulbs.