algorithmdata-structurestreebinary-treepostorder

How many rooted binary trees with exactly 11 nodes are pleasantrees?

A label rooted tree with exactly N nodes is a pleasant tree if and only if:

  1. each of its nodes is labeled with a positive integer between 1 to N.
  2. No 2 nodes have the same label
  3. A post-order traversal of the tree visited the nodes in increasing numerical order of its label.

for example, all of these are pleasant trees.enter image description here

Solution

  • This is essentially the same question as finding the number of possible binary search trees with n nodes.

    The difference is that in this problem the order of the nodes is left subtree < right subtree < current node, instead of left subtree < current node < right subtree in a binary search tree.