Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have a binary search tree of size $N$.
The tree is height balanced: difference of heights of a node's subtrees is no more than 1 (true for RB or AVL trees).
$K$ is the number of nodes that have a non-empty right subtree.
If the tree is intentionally created to minimize $K$, then what is $\min(K)$?
Given your requirement to minimize $K$, the number nodes with right subtree, while maintaining subtree height difference of at most 1,you should start with the AVL tree $T_h$ of height $h$, with minimum number of nodes. It is known that such tree has $F_{h+2} - 1$ nodes, where $F_i$ is the $i$th Fibonacci number (here I am using the version where $F_0=F_1=1$). Note that $T_h$ can be recursively constructed from a root $r$ with left subtree $T_{h-1}$ and right subtree $T_{h-2}$. We force the right subtrees of all nodes in the tree to have lesser nodes for the purpose of minimizing $K$.
Notice that since $T_h$ already has minimal number of nodes and must be balanced, all nodes whose subtree has height $\ge 2$ must have left and right subtrees. The number of such nodes should give you the minimum value for $K$.
To count these nodes, you can remove from $T_h$ nodes with height 0 (these are the leaves) and nodes with height 1 (since this nodes have no right subtree from the way $T_h$ is constructed). I claim that after removal you'll get the AVL tree $T_{h-2} $, that has $K =F_h - 1$ nodes.
