1
$\begingroup$

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)$?

$\endgroup$
2
  • $\begingroup$ Please edit your question to include this information in the question, and make sure it is clear and reads well for someone who encounters it for the first time. We don't want someone to have to read the comments to understand what is being asked. We are looking to build up a high-quality of archive of knowledge in the form of questions and answers, so we have high expectations for the quality of questions posted here. $\endgroup$
    – D.W.
    Dec 12, 2022 at 21:35
  • $\begingroup$ @D.W. I removed any notion of probability from the question. $\endgroup$ Dec 12, 2022 at 21:55

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.