SDE - Intern

You have been given a Binary Tree of integers. You are supposed to return the level order traversal of the given tree.

For example:

For the given binary tree

The level order traversal will be {1,2,3,4,5,6,7}.

You have been given a curve whose edges are parallel to either x-axis or y-axis. You need to return another curve which will pass through the midpoints of all the edges of the curve. The curve will be given in the form of a linked list, where each node represents the coordinates of the curve.

The curve to be returned will also be in the form of a linked list, where each node may represent the coordinates of the midpoints of the edges.

Note

1. The coordinates of the curve will be given in non-descending order of x coordinate from start to end of the linked list and for every two adjacent coordinates either the x-coordinate or the y-coordinate will be the same.
2. All the coordinates will be pairwise distinct i.e there are no two coordinates (x1, y1) and (x2, y2) such that x1 = x2 and y1 = y2.
3. The first coordinate and the last coordinate in the input can be assumed as the starting point and the ending point of the curve respectively.
4. You may assume that the starting point and ending point of the curve will be the midpoint of the first edge, and the last edge of the input curve( in the order of input coordinates) respectively.
5. If the coordinates of the midpoint are not whole numbers, you may take the floor value of the coordinates. For example, the midpoint (3.5, 5) will be taken as (3, 5).

You have been given a Binary Tree of 'n' nodes, where the nodes have integer values

Print the left view of the binary tree.

Example :

If the input tree is as depicted in the picture: 

The Left View of the tree will be:  2 35 2 

There is a Binary Search Tree (BST) consisting of ‘N’ nodes. Each node of this BST has some integer data.

You are given the root node of this BST, and an integer ‘X’. Return true if there is a node in BST having data equal to ‘X’, otherwise return false.

A binary search tree (BST) is a binary tree data structure that has the following properties:

1. The left subtree of a node contains only nodes with data less than the node’s data.

2. The right subtree of a node contains only nodes with data greater than the node’s data.

3. The left and right subtrees must also be binary search trees.

Note:

It is guaranteed that all nodes have distinct data.

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.