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: 
Interesting question!

My earlier attempt was moronically wrong!

Here is another attempt (hopefully correct this time).

I am assuming the tree is connected.

Suppose for each node n of the tree, you had a set of descendants of n, Sn with the property that

* For each member x of Sn, the unique path from n to x is a Binary Search Tree (it is only a path, but you can still consider it a tree).
* For every descendant y of x, such that the path from n to y is a BST, y is in Sn.

The set of nodes Sn, gives you the largest BST rooted at n.

We can construct Sn for each node by doing a depth first search on the tree, and passing in the path information (the path from root to the current node) and updating the sets of the nodes in the path by backtracking along the path.

When we visit a node, we walk up the path, and check if the BST property is satisfied for that segment of the path walked up so far. If so, we add the current node to the corresponding set of the node of the path we just walked to. We stop walking the path the moment the BST property is violated. Checking if the path segment we walked so far is a BST can be done in O(1) time, for a O(path\_length) time total processing time, for each node.

At the end, each node will have its corresponding Sn populated. We can walk the tree now and pick the node with the largest value of Sn.

The time taken for this is the sum of depths of the nodes (in the worst case), and that is O(nlogn) in the average case (see Section 5.2.4 of <http://www.toves.org/books/data/ch05-trees/index.html>), but O(n^2) in the worst case.

Perhaps a cleverer way to update the sets will guarantee a reduction in the worst case time.

The pseudo-code could be something like:

```
static Tree void LargestBST(Tree t)
{
    LargestBST(t, new List<Pair>());
    // Walk the tree and return the largest subtree with max |S_n|.
}

static Tree LargestBST(Tree t, List<Pair> path)
{
    if (t == null) return;

    t.Set.Add(t.Value);

    int value = t.Value;
    int maxVal = value;
    int minVal = value;

    foreach (Pair p in path)
    {
        if (p.isRight)
        {
            if (minVal < p.node.Value)
            {
                break;
            }
        }

        if (!p.isRight)
        {
            if (maxVal > p.node.Value)
            {
                break;
            }
        }

        p.node.Set.Add(t.Value);

        if (p.node.Value <= minVal)
        {
            minVal = p.node.Value;
        }

        if (p.node.Value >= maxVal)
        {
            maxVal = p.node.Value;
        }
    }

    Pair pl = new Pair();
    pl.node = t;
    pl.isRight = false;

    path.Insert(0, pl);
    LargestBST(t.Left, path);

    path.RemoveAt(0);

    Pair pr = new Pair();
    pr.node = t;
    pr.isRight = true;

    path.Insert(0, pr);

    LargestBST(t.Right, path);

    path.RemoveAt(0);

}

```
```
root(Tree L A R) = A

MaxBST(NULL) = (true, 0, NULL)
MaxBST(Tree L A R as T) = 
  let
    # Look at both children
    (L_is_BST, L_size, L_sub) = MaxBST(L)
    (R_is_BST, R_size, R_sub) = MaxBST(R)
  in
  # If they're both good, then this node might be good too
  if L_is_BST and R_is_BST and (L == NULL or root(L) < A) and (R == NULL or A < root(R))
  then (true, 1 + L_size + R_size, T)
  else
       # This node is no good, so give back the best our children had to offer
       (false, max(L_size, R_size), if L_size > R_size then L_sub else R_sub)

```

Looks at each tree node exactly once, so runs in O(N).

Edit: Crud, this doesn't consider that it can leave out some parts of a subtree. When I read subtree, I assumed "the entire tree rooted at some node". I may come back to fix this later.