Finding the number of nodes in 2-3 tree while left sub-tree of the root has 3 children,right sub-tree of the root has 2 children

Question

Suppose there is a 2-3 tree with n nodes.

Each node in the left sub-tree of the root has 3 children. (except the leaves).

Each node in the right sub-tree of the root has 2 children. (except the leaves).

How am I supposed to find how many nodes exist in the right/left sub-tree of the root?

Denote n':= nodes number in the right root sub-tree.

Then,Nodes number in the left root sub-tree is (n-1)-n'.

How am I supposed to find n' (to write n' as an expression of n)?

I am a little bit confused.

Thanks !

user_477008 · Answer

Let the total height of the tree be h. Since it's a 2-3 tree, both the left and right subtree have heigth h−1. The number of nodes in the right subtree is 2^h − 1, and the number of nodes in the left subtree is (3^h − 1)/2. Beyond that, I don't know anything really interesting to say. The quotient nʹ / n doesn't come out very pretty, but it approaches zero quite quickly as h increases.