Loading...
Loading...
Loading...
Aditya's data structures assignment produced a binary tree that is not a binary search tree everywhere. His teacher still wants to know how much of it is usable.
A subtree here means a node together with all of its descendants. Print the number of nodes in the largest subtree that is a valid binary search tree: for every node in it, all values on its left are smaller and all values on its right are larger. Print 0 for an empty tree.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. An empty tree is N.Example 1
Input
5 3 8 N 6 N N N N
Output
2
The whole tree fails, because 6 is left of 5 but larger. The subtree of 3 (3 and 6) is valid, with 2 nodes.
Example 2
Input
10 5 15 1 8 N 7 N N N N N N
Output
3
The subtree of 5 holds 1, 5 and 8 and is valid. The subtree of 15 fails, because 7 is right of 15.
Try the problem first. Open one hint at a time.
Checking every node with a separate full check repeats a lot of work. Can each subtree report about itself to its parent?
For a subtree, it is enough to know: is it valid, how many nodes it has, and its smallest and largest values.
A node forms a valid subtree when both children are valid, the left largest is below the node, and the right smallest is above it.
Give an empty subtree the smallest value +infinity and the largest value -infinity, so it never breaks the check.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor