Question: I know the theritical definition for distributed computing and interproces communication.

But in real time I was not able to come to conclusion that when we go for distributed or interprocess.

Tell me some scenario where we can go for distributed computing or interprocess communication by example.

Answer: 
This answer previously contained an O(n log n) algorithm based on link/cut trees. Here is a simpler **O(n)** solution.

The core is a procedure that accepts a node, the unique maximum BSST rooted at its left child, the unique maximum BSST rooted at its right child, and pointers to the left-most and right-most elements of these BSSTs. It destroys its inputs (avoidable with persistent data structures) and constructs the unique maximum BSST rooted at the given node, together with its minimum and maximum elements. All BSST nodes are annotated with the number of descendants. As before, this procedure is called repeatedly from a post-order traversal. To recover the sub-tree, remember the root of the largest BSST; reconstructing it requires only a simple traversal.

I'll treat the left BSST only; the right is symmetric. If the root of the left BSST is greater than the new root, then the entire sub-tree is removed, and the new root is now left-most. Otherwise, the old left-most node is still left-most. Starting from the right-most node of the left BSST and moving upward, find the first node that is less than or equal to the root. Its right child must be removed; note now that due to the BST property, *no other nodes need to go!* Proceed to the root of the left BSST, updating the counts to reflect the deletion.

The reason this is O(n) is that in spite of the loop, each edge in the original tree is in essence traversed only once.

---

EDIT: collectively, the paths traversed are the maximal straight-line paths in a BST, except for the left spine and the right spine. For example, on the input

```
              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / \             / \
    /   \           /   \
   /     \         /     \
  B       F       J       N
 / \     / \     / \     / \
A   C   E   G   I   K   M   O

```

here are the recursive calls on which each edge is traversed:

```
              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / h             h \
    /   h           h   \
   /     h         h     \
  B       F       J       N
 / d     d h     h l     l \
A   C   E   G   I   K   M   O

```
**LARGEST BINARY SEARCH TREE IN A BINARY TREE:**

**There are two ways we can approach this problem,**

i)Largest BST not induced (From a node, all its children need not satisfy the BST condition)

ii)Largest BST induced (From a node , all its children will satisfy the BST condition)

We will discuss about the largest BST(Not Induced) here. We will follow bottom up approach(Post order traversal) to solve this.

a)Reach the leaf node

b)A tree node(from the leaf) will return a TreeNodeHelper object which has the following fields in it.

```
public static class TreeNodeHelper {
        TreeNode node;
        int nodes;
        Integer maxValue;
        Integer minValue;
        boolean isBST;

        public TreeNodeHelper() {}

        public TreeNodeHelper(TreeNode node, int nodes, Integer maxValue, Integer minValue, boolean isBST) {
            this.node = node;
            this.nodes = nodes;
            this.maxValue = maxValue;
            this.minValue = minValue;
            this.isBST = isBST;
        }      
    }

```

c)Initially from the leaf node, nodes=1,isBST=true,minValue=maxValue=node.data . And further, the nodes count will be increased if it satisfies the BST condition.

d)With the help of this, we will check the BST condition with current node. And we will repeat the same till root. 

e)From each node two objects will be returned. one for last maximum BST and another one for current BST satisfying nodes. So from each node(above leaf) (2+2)=4 (2 for left subtree and 2 for right sub tree) objects will be compared and two will be returned.

f) The final maximum node object from root will be the largest BST

**PROBLEM:**

There is a problem in this approach. While following this approach, if a subtree is not satisfying the BST condition with the current node, we can't simply ignore the subtree(even it has less number of nodes). For example 

```
 55
  \
   75
  /  \
 27  89
    /  \
   26  95
      /  \
     23  105
         /  \
        20  110

```

From the leaf nodes(20,110) the objects will be tested with node(105), it satisfies the condition. But when it reaches node(95) the leaf node(20) does not satisfy the BST condition. Since this solution is for BST(Not induced) we should not ignore node(105) and node(110) which satisfies the condition. So from node(95) we have to backtrack again testing BST condition and catch those nodes(105, 110).

The complete code for this implementation is available in this link

<https://github.com/dineshappavoo/Implementation/tree/master/LARGEST_BST_IN_BT_NOT_INDUCED_VER1.0>