Software Developer

You are given an array of integers and a number ‘K’. You can pair two elements in the array 'ARR' if the absolute difference between them is strictly less than ‘K’. Your task is to find the maximum possible sum of disjoint pairs among all the pairs of numbers you can obtain.

The sum of a pair is the sum of the elements in the pair.

For Example:

Input: ARR[] = {3, 5, 10, 15, 17, 12, 9}, K = 4
Output: 62

Then disjoint pairs with the absolute difference less than K are 
(3, 5), (10, 12), (15, 17)  
So maximum sum which we can get is 3 + 5 + 12 + 10 + 15 + 17 = 62

Note:

Note that an alternate way to form disjoint pairs is, (3, 5), (9, 12), (15, 17), but this pairing produces a lesser sum.

Ninja is learning tree data structure these days. While learning, she came across learn about the Binary Search tree. She found BST quite interesting. She decided to make her own Binary Search Tree. Being a newbie, she made a mistake and swap two nodes of the Binary Search Tree.

Your responsibility being an expert and a good friend is to correct the Binary Search Tree made by Ninja and recover the correct Binary Search Tree.

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

This is the binary search tree made by Ninja. But here, the left node of 8 is greater, and the right node is smaller.
If we swap the right and the left node of 8 Ninja’s Binary Search Tree will become correct.

This is the correct binary Search Tree.