Description
Write a program to compute the number of nodes in every subtree.
For example, in figure below, the subtree rooted at node 6 contains three nodes: 1, 6, and 9.
Constraints:
0 < n ≤ 100000
Input
The input consists of one line containing n integers that are to be inserted into a binary search tree (BST) in the given order.
Ex. 4 6 2 9 5
Output
The output should list, one node per line, each node’s value followed by the total number of nodes in the subtree rooted at that node.
The nodes must be printed in in-order traversal.
Ex. 2 1
4 5
5 1
6 3
9 1