jeremiah.bullfrog
BAN USERSure but you're calling GetMinSum potentially many times for each node. How about, 2 extensible arrays that are the depth of the tree (or stacks), and a globally least/greatest path sum, and one of the stacks for the best path so far.
Traverse the tree, keeping the sum-so-far on the way down at each node, and pushing the current node into the temporary stack, as you go (pop it on the way back up of course). At the leaf nodes, see whether the sum-so-far is greater / less than the global one, and if so copy the temporary stack to the global one.
At the end, print the global stack.
It would be nice if you could just do a pre-order traversal, and count the number of nodes that you encounter that are in order, together. A nice, O(n) solution. But it won't work; you could have a big BST eg on the left, the root happens to be larger than all the left side (so it's still in order), and then the left-most node of the right tree is in-order too, by chance. But the rest of the right tree is not sorted. Our longest sequence found this way thus isn't a BST.
Is a 'subtree' defined as perforce including the leaves? If so it's pretty easy I think:
If you're a leaf, you're a (trivial) BST, return 1, and your value (a tuple, somehow). if you're a left tree, return the value of your right-most (largest) child, as well (if a right child-tree, return the value of the left-most child). Now, our max-subtree routine can do: if my left subtree is giving non-zero for BST size, and its biggest child is < my own value, and my right subtree is non-zero for BST size, and its left-most value is > my own, well, add the two sizes together, + one for myself, and return that BST size. Otherwise return 0 (if we're not a sub-BST, it doesn't matter what our largest/smallest children are). I guess you'd keep a global max-BST size seen so far variable, and print that at the end.
If you can have 'interior-only' BSTs, ie the interior nodes are ordered but some of the leaves are not, I think it'd have to be some dynamic programming thing.
Yeah, CC needs an easier way to find dups; it's too much work right now.
- jeremiah.bullfrog October 10, 2011'a website has lots of posts; how would you go about finding a first-cut of similar ones, to make it easier for people to find dups?'. I have to say, stackoverflow already does this better - it brings up a list of possibly related posts, even when you're writing your question. Though, there are so many of them. Hum; a better way to do that could be a product to sell them...
fwiw I did find an earlier dup from Jul 2011 and reported this one, but I could swear I saw one in early 2010 at latest.