Number of nodes in the two subtrees of a complete binary tree

Question

Is there a mathematical formula to calculate the number of nodes in the Left and Right of a complete binary tree?

There exists a similar problem on Stack Overflow - Find number of nodes in left and right subtree of a complete binary tree if total number of nodes are given in O(1).

But here I want to calculate the number of nodes in the left (L) and right (R) subtreee of a complete binary Tree programmatically.

I suspect there must be a concrete math formula to calculate L and R, given N, where N is the total number of nodes. Does anyone know of it?

I've been trying to calculate the height of the binary tree and then use height to calculate L and R, but I'm unsuccessful so far.

This is what I tried, but it's wrong:

h = math.floor(math.log(N,2))
L = min(N-1, 1+2**(h-1))
R = N - 1 - L

You should ask in math.stackexchange.com

Leandro Bardelli
– Leandro Bardelli

2023-04-16 22:03:09 +00:00
Commented Apr 16, 2023 at 22:03 — Leandro Bardelli
– Leandro Bardelli, Commented Apr 16, 2023 at 22:03

trincot · Accepted Answer · 2023-04-17 09:42:32Z

Let ℎ be the tree's height, i.e. the number of edges on the root-to-leftmost-leaf path. For a given number of nodes 𝑛, we have ℎ=⌊log_₂𝑛⌋

For a given height ℎ the minimum number of nodes in the left subtree is 𝑚=2^ℎ−1.

The actual number of nodes in the left subtree of a tree with 𝑛 nodes is 𝑚 + min(𝑚−1, 𝑛−2𝑚).

The number of nodes in the right subtree can be derived from that, since the sum of the nodes in both subtrees should be 𝑛−1.

Here is an implementation in JavaScript, and the formula is run for 𝑛 between 1 and 16:

// This function returns two integers (as array): 
// the sizes of the two subtrees given the number of nodes in a complete binary tree
function subTreeSizes(n) {
    if (n < 2) return [0, 0]; // There are no left/right subtrees
    const height = Math.floor(Math.log2(n)); // Number of edges on leftmost path
    const minLeftSize = 1 << (height - 1);
    const leftSize = minLeftSize + Math.min(minLeftSize - 1, n - 2*minLeftSize);
    const rightSize = n - 1 - leftSize;
    return [leftSize, rightSize];
}

console.log("Nodes, left size, right size:");
for (let n = 1; n <= 17; n++) {
    console.log(n, ...subTreeSizes(n));   
}

Collectives™ on Stack Overflow

Number of nodes in the two subtrees of a complete binary tree

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related