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: 
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)`
**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>