StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Interesting question!</p> <p>My earlier attempt was moronically wrong!</p> <p>Here is another attempt (hopefully correct this time).</p> <p>I am assuming the tree is connected.</p> <p>Suppose for each node n of the tree, you had a set of descendants of n, S<sub>n</sub> with the property that</p> <ul> <li><p>For each member x of S<sub>n</sub>, 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).</p></li> <li><p>For every descendant y of x, such that the path from n to y is a BST, y is in S<sub>n</sub>.</p></li> </ul> <p>The set of nodes S<sub>n</sub>, gives you the largest BST rooted at n.</p> <p>We can construct S<sub>n</sub> 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.</p> <p>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.</p> <p>At the end, each node will have its corresponding S<sub>n</sub> populated. We can walk the tree now and pick the node with the largest value of S<sub>n</sub>.</p> <p>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 <a href="http://www.toves.org/books/data/ch05-trees/index.html" rel="nofollow noreferrer">http://www.toves.org/books/data/ch05-trees/index.html</a>), but O(n^2) in the worst case.</p> <p>Perhaps a cleverer way to update the sets will guarantee a reduction in the worst case time.</p> <p>The pseudo-code could be something like:</p> <pre><code>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); } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload