SDE - Intern

You have been given a Binary Search Tree (BST). Your task is to flatten the given BST to a sorted list. More formally, you have to make a right-skewed BST from the given BST, i.e., the left child of all the nodes must be NULL, and the value at the right child must be greater than the current node.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a value greater than all the values in the node's left subtree and less than those in its right subtree.

Follow Up :

Can you solve this in O(N) time and O(H)  space complexity?

You are given a linked list of 'N' nodes where nodes can contain values 0, 1, and 2 only. Your task is to sort the linked list.

A Ninja was learning how to calculate the binomial coefficient. But, learning that alone won’t help the ninja since a lot of problems are required to be solved as homework. Since the ninja is old-fashioned and doesn’t know that a computer can do the same homework in a matter of a few seconds you will have to help with the problems.

You need to complete a function for the ninja that can calculate the binomial of a number where when given two integers 'N' and 'R', the program can calculate its respective binomial coefficient nCr. Since the answer may be very large, calculate the answer modulo 10^9 + 7.

For Example:

Input: 'N' = 5, 'R' = 2
Output: 10

The value of 5C2 is 10
After taking the modulo with 10^9 + 7 we get 10.

You have been given a Binary Tree of integers. You are supposed to return the largest subtree sum in the given Binary Tree.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Example :

For the given binary tree:

Subtree with the largest sum is highlighted in the above image. The sum is (-2 + 4 + 7) = 9