SDE - 1

You are given an arbitrary binary tree consisting of N nodes. Your task is to find the largest subtree sum.

Note :

1. The value of any node will not be equal to zero.
2. Subtree of a node X is all the nodes that are below X and X itself.
3. For example in the tree given below, nodes 1, 2 and 3 are in subtree of 1.

4. Subtree sum of X is the sum value of all the nodes in subtree of X.  
5. Binary tree is a tree wherein each node has at most two children.  
6. Any two nodes may have the same value associated with it.

You're given a positive integer represented in the form of a singly linked-list of digits. The length of the number is 'n'.

Add 1 to the number, i.e., increment the given number by one.

The digits are stored such that the most significant digit is at the head of the linked list and the least significant digit is at the tail of the linked list.

Example:

Input: Initial Linked List: 1 -> 5 -> 2

Output: Modified Linked List: 1 -> 5 -> 3

Explanation: Initially the number is 152. After incrementing it by 1, the number becomes 153.

You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.

Note :

Try to solve the problem in 'Single Scan'. ' Single Scan' refers to iterating over the array/list just once or to put it in other words, you will be visiting each element in the array/list just once.

You are given a string ‘str’ of size ‘N’. Your task is to remove consecutive duplicates from this string recursively.

For example:

If the input string is ‘str’ = ”aazbbby”, then your output will be “azby”.
Note that we are just removing adjacent duplicates.

Ninja is stuck in a maze which is in a form of a binary tree. He needs your help in order to get out.

Ninja is presently at the node ‘X’. The only exit points of the maze are the leaf nodes of the tree. You need to tell him the distance to the nearest exit point from his current location. This will help him decide which path he should take in order to escape from the maze.

Example:

Suppose, Ninja is stuck at node 62. The possible exit points in the maze are: 40, 10, and 20. From all the possible exit points the closest ones are 10 and 20 which are at a distance of 1 unit.

You have been given a Binary Tree of 'N' nodes where the nodes have integer values.

Your task is to find the largest number that could be formed by concatenating all its nodes values.

For example:

For the given binary tree:   

Output: 96553210    

Explanation: After concatenating all the numbers in the above binary tree this is the largest number that can be formed.