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

```
The previous algorithm *(see revisions)* was `O(n^2)` - we can generalize it to `O(n log n)` by noticing the facts that:

1. If b is the root of the largest BST and `b.left.value < b.value`, then `b.left` is also in the BST (same for `b.right.value ≥ b.value`)
2. If b is the root of the largest BST and a is also in the BST, then every node between a and b is in the BST.

So if c is between a and b, and c is not in the BST rooted by b, neither is a *(due to (2.))*. Using this fact, we can easily determine if a node is in the BST rooted by any given ancestor. We'll do this by passing a node into our function along with a list of its ancestors, and the associated min/maxValues that the current child-node would have to satisfy if indeed that ancestor were the root of the largest BST (we'll call this list `ancestorList`). We'll store the entire collection of potential-roots in `overallRootsList`

Let's define a structure called potentialRoot as follows:

> 
> Each **potentialRoot** contains the following values:  
> 
>  \* **node**: The node we are considering for the root of the BST  
> 
>  \* **minValue and maxValue**: the range another node must fall between to be part of the BST rooted by node *(different for every node)*  
> 
>  \* **subNodes**: A list of the rest of the nodes in the largest BST rooted by node
> 
> 
> 

The pseudo code looks like this *(note that all lists mentioned are lists of potentialRoots)*:

```
FindLargestBST(node, ancestorList):
    leftList, rightList = empty lists
    for each potentialRoot in ancestorList:
        if potentialRoot.minValue < node.Value ≤ potentialRoot.maxValue:
            add node to potentialRoot.subNodes (due to (1.))
            (note that the following copies contain references, not copies, of subNodes)
            add copy of potentialRoot to leftList, setting maxValue = node.Value
            add copy of potentialRoot to rightList, setting minValue = node.Value

    add the potentialRoot (node, -∞, +∞) to leftList, rightList, and overallRootsList
    FindLargestBST(node.left, leftList)
    FindLargestBST(node.right, rightList)

```

At the end `overallRootsList` will be a list of `n` potentialRoots, each with a list of subNodes. The one with the largest subNodes list is your BST.

Since there are < treeHeight values in `ancestorList`, then (assuming the tree is balanced), the algorithm runs in `O(n log n)`