Software Engineer

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

You are given an array, ‘arr’, your task is to partition the array into such a way that, that all the elements in the left half of the array are smaller than or equal to all the elements in the right half the array. Each partition should have at least one element. You have to return the smallest length of the left partition possible.

Note:

The left half of the array must be the smallest possible.
If there is no partition return the size of the array.

For example:

You are given, ‘arr’ = [8, 3, 1, 4, 9, 10], this array can be partitioned at index ‘3’ so the left array is [8, 3, 1, 4] and the right array is [9, 10]. Hence the answer is 4.

You are given an arbitrary binary tree consisting of N nodes where each node is associated with a certain value. You need to check whether the given tree is a sum tree or not.

A binary tree is a sum tree if the value of each node is equal to the sum of nodes present in the left and the right subtree. An empty tree is a sum tree with 0 sums. A leaf node is also considered a sum tree with a sum equal to the value of the leaf node.

You have been given a Binary Tree of 'n' nodes, where the nodes have integer values. Your task is to return the In-Order traversal of the given binary tree.

For example :

For the given binary tree:

The Inorder traversal will be [5, 3, 2, 1, 7, 4, 6].