Abstract   In a binary tree  T  of  N  leaves, the left (right) level  l   i   ( r   i  ) of leaf  i  is the number of left (right) edges in path from the root to that leaf. The level  n   i   of leaf  i  is  n   i   =  l   i   +  r   i  . Kraft-McMillan's characteristic inequality gives a necessary and sufficient condition for a multiset of integers [ n  1 ,  n  2 , …,  n   N  ] to be the  length ensemble  of a binary tree  T . Similarly, Yeung's characteristic inequality gives a necessary and sufficient condition for a vector of integers ( n  1 ,  n  2 , …,  n   N  ) to be the  length vector  of a binary tree  T .  In this paper, we study characteristic inequalities for the  path ensemble  [( l  1 ,  r  1 ), ( l  2 ,  r  2 ), …, ( l   n  ,  r   N  )} and the  path vector  [( l  1 ,  r  1 ), ( l  2 ,  r  2 ), …, ( l   N  ,  r   N  )] of a binary tree  T . As an application of our results, we show a technique to construct  U - R  systems for the partial sums problem starting from weighted binary trees.
['Roberto De Prisco', 'Giuseppe Persiano']
Characteristic inequalities for binary trees