2

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

Romil
  • 55
  • 3
  • 1
    That's the same as the number of unlabeled binary trees with N nodes -- just label one in postorder to get a "pleasantree". People who ask these kinds of questions don't usually make up unnecessary conditions and funny names. You might want to check to make sure you got the question right. Anyway, the answer to the question posed is C_n: https://en.wikipedia.org/wiki/Catalan_number – Matt Timmermans Jul 31 '20 at 01:16

1 Answers1

2

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.

nullptr
  • 505
  • 3
  • 10