SDE - 1

You are given an arbitrary binary tree, a node of the tree, and an integer 'K'. You need to find all such nodes which have a distance K from the given node and return the list of these nodes.

Distance between two nodes in a binary tree is defined as the number of connections/edges in the path between the two nodes.

Note:

1. A binary tree is a tree in which each node has at most two children. 
2. The given tree will be non-empty.
3. The given tree can have multiple nodes with the same value.
4. If there are no nodes in the tree which are at distance = K from the given node, return an empty list.
5. You can return the list of values of valid nodes in any order. For example if the valid nodes have values 1,2,3, then you can return {1,2,3} or {3,1,2} etc.

Example :

Consider this tree above. The target node is 5 and K = 3. The nodes at distance 1 from node 5 are {2}, nodes at distance 2 from node 5 are {1, 4} and nodes at distance 3 from node 5 are {6, 3}.

Ninja is assigned with the duty of creating some problems on algebra or we can say questions on evaluating the expression. After creating those questions he has to send it so that the answer sheet according to the questions can be made. So he thinks someone might get his paper in between so he thinks of an encryption technique.

So in this encryption technique, he writes his expression in the form of a binary tree where leaf nodes represent the value and all other nodes represent the binary operators like ‘-’, ‘+’, ‘/’, ‘*’.

So now ninja has to find a way of decrypting his own technique as he has to tell the way of decrypting his own expression so that the answer team is able to solve his expression.

So your task is to write the code that can evaluate the given expression in the form of a binary tree where each node must have two children except leaf nodes and leaf nodes represent integer while other nodes represent binary operators like ‘-’, ‘+’, ‘/’, ‘*’.

Example:

Consider the following binary search tree so the evaluation of the expression is ( 4 *  ( 5 - ( 2+ 7 ) ) ) = ‘-16’

Note:

You have been given the root of the tree.

You have been given a binary tree of integers. You have to return all the diagonal paths of the binary tree. A diagonal path is one in which all the nodes pass through -1 slope line.

A binary tree is a tree in which each parent node has at most two children.

Note:

Order of return of diagonal path’s array/vector: The rightmost diagonal path must come first, and so on.
Every parent node comes first then the child node. In other words, return the diagonal element from top to bottom.

Example

Consider the given binary tree.

There are 4 diagonal paths:
1 3 6
2 5 9
4 8
7
You need to return ‘1 3 6 2 5 9 4 8 7’.

Let's consider this example

Diagonal paths are:
1 3 6
2 5
4

You need to return ‘1 3 6 2 5 4’.