Research Intern

You are given a binary search tree and an integer ‘S’. Your task is to find all the pairs of nodes in the BST which sum to the value ‘S’. If no such pair exists, then print -1 - 1.

Note:

You can use extra space of the order of not more than O(log n).

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.

Note:

1. All the elements of the Binary Search Tree are unique.
2. You can’t use the same node value/element of BST twice.

You have been given the ‘ROOT’ of a binary tree having ‘N’ nodes, you need to find the largest value in each row or level of the binary tree.

For Example

For the above binary tree, 
Max value at level 0 = 6.
Max value at level 1 = max(9 , 3) = 9
Max value at level 2 = max (4, 8, 2) = 8

You are given an arbitrary binary tree consisting of N nodes, your task is to find all the nodes of the tree that do not have a sibling.

A binary tree is a tree where every node has at most two child nodes.

Two nodes in a tree are called siblings if they are children of the same parent node i.e they have the same immediate ancestor node.

Note:

1. The root node is not considered as the node with no sibling.
2. If there are no such nodes, return -1.

For example, consider the following binary tree:

Here node 4 and 7 do not have any siblings.