SDE - 1

You are given a string 'S' that consists of I’s and D’s pattern only. 'I' is for increasing, and 'D' is for decreasing. Your task is to return the string that consists of a minimum number following that pattern.

Note:

1) Digits of the number should be in the range [1,9] and can’t repeat.

2) The length of the string should be less than or equal to 8.

Given a binary tree having ‘N’ number of nodes. Your task is to find the sum of all left nodes present in the input binary tree. That is, you need to take the sum of all nodes which are the left child of some node.

Note :

1. A binary tree is a tree in which each node can have at most two children. 
2. The given tree will be non-empty i.e the number of non-NULL nodes will always be greater than or equal to 1.
3. Multiple nodes in the tree can have the same values, all values in the tree will be positive.

Given an array ‘ARR’ of size ‘N,’ swap the Kth element from beginning with the Kth element from the end.

For example:

If ‘N’ = 5 and K = 2
[1, 2, 3, 4, 5]

Then the output will be [1, 4, 3, 2, 5].

You are given an array 'ARR' of integers of length N. Your task is to find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can have negative numbers as well.

For example, the input [3, 4, -1, 1] should give output 2 because it is the smallest positive number that is missing in the input array.

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to return the size of the largest subtree of the binary tree which is also a BST.

A binary search tree (BST) is a binary tree data structure which 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:

Given binary tree:

In the given binary tree, subtree rooted at 2 is a BST and its size is 3.

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.

The process of the COVID-19 vaccine has started in a special city structured like a binary tree. Ninja has been appointed as a doctor to do this vaccination. Some of the houses in the city are already vaccinated and Ninja wants to vaccinate the people in the remaining houses.

But the problem is that Ninja doesn’t remember the address of these remaining houses. However, he remembers that the houses that are still not vaccinated are at a ‘K’ distance from the last houses in the city. Ninja wants to find out how the number of these non-vaccinated houses.

Note :

The last house is similar to a leaf node in a binary tree and a house that is present at ‘K’ distance from the last house should be the direct ancestor of this last house.

For Example :

In this example :
2 is the direct ancestor of 4 and 5.
1 is the direct ancestor of 2, 3, 4, and 5.

You have been given a Binary Tree of ‘N’ nodes, where the nodes have integer values. Your task is to print all nodes that don’t have a sibling node.

Note:

1. Node ‘U’ is said to be a sibling of node ‘V’ if and only if both ‘U’ and ‘V’ have the same parent.
2. Root 1 is a sibling node.