SDE - 2

Given a binary tree with N number of nodes, check if that input tree is Partial BST (Binary Search Tree) or not. If yes, return true, return false otherwise.

A binary search tree (BST) is said to be a Partial BST if it follows the following properties.

• The left subtree of a node contains only nodes with data less than and equal to the node’s data.
• The right subtree of a node contains only nodes with data greater than and equal to the node’s data.
• Both the left and right subtrees must also be partial binary search trees.

Example:

Input:

Answer:

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2:
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2.
For node 5:
The left and right subtree for node 5 is empty.

Level 3:

For node 1:
The left and right subtree for node 1 are empty.
For node 3:
The left and right subtree for node 3 are empty.
Because all the nodes follow the property of a Partial binary 
search tree, the above tree is a Partial binary search tree.

Given a binary tree with 'N' number of nodes, convert it to a Greater Tree such that data of every node of the original BST is changed to the original node’s data plus the sum of all node’s data greater than or equal to the original data of the node in the BST.

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

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

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

• Both the left and right subtrees must also be binary search trees.

Example:

Answer:

Because only 5 is greater than 4 in the above BST, node 4 will be updated to 9 (4 + 5 = 9).

Nodes 3, 4, and 5 are greater than 2, hence node 2 will be modified to 14 (2 + 3 + 4 + 5 = 14). 

Node with data 5 will remain the same because there is no node in the BST with data greater than 5.

Nodes 2,3, 4, and 5 are greater than 1, hence node 1 will be modified to 15 (1 + 2 + 3 + 4 + 5 = 15).   

Nodes 4 and 5 are greater than 3, hence node 3 will be modified to 12 (3 + 4 + 5 = 12). 

You're given a string 'S' consisting of "{", "}", "(", ")", "[" and "]" .

Return true if the given string 'S' is balanced, else return false.

For example:

'S' = "{}()".

There is always an opening brace before a closing brace i.e. '{' before '}', '(' before ').
So the 'S' is Balanced.

You are given a multi-level linked list of 'N' nodes, each node has a next and child pointer which may or may not point to a separate node. Flatten the multi-level linked list into a singly linked list. You need to return the head of the updated linked list.

Example:

Flatten :

All the different rows are merged into a single row.

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.

Discussed about past Projects, challenges faced, disagreements with manager, why looking for job switch,  leadership principle questions were asked.