Question 12373 – Data-Structures

First, consider the tree on the left.


On the right, the nine nodes of the tree have been assigned numbers from the set {1, 2,. .., 9} so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree are less than all numbers in the other subtree). How many such assignments are possible? Hint: Fix a value for the root and ask what values can then appear in its left and right subtrees.

Correct Answer: B