Find number of nodes in left and right subtree of a complete binary tree if total number of nodes are given in O(1)

Question

I want to find count of nodes in left and right subtree of complete binary tree if total nodes are given,

for example,

n = 5 ===> left -> 3 right -> 1

n = 8 ===> left -> 4 right -> 3

where n is total number of nodes in a binary tree

is there any formula or O(1)/optimal solution to do this?

Answer 1

is there any formula or O(1)/optimal solution to do this?

Yes.

Write the given 𝑛 (number of nodes) in binary notation, and turn every 1 to a 0, except the most significant 1. Call this number 𝑝. Define 𝑘 as 𝑛 − 𝑝, so that in binary it is the same as 𝑛, but with its most significant digit removed. The number of nodes in the right subtree wil be equal to max(𝑘, 𝑝 / 2 − 1).

It is then a piece of cake to know how many are in the left subtree, because the sum of nodes in both subtrees plus 1 (for the root node) must be equal to 𝑛.

Your example

When 𝑛 = 5, we note that down in binary as 0b101. We can see that 𝑝 = 0b100 and 𝑘 = 0b001. So the right subtree has max(𝑘, 𝑝/2 − 1) nodes, i.e. max(1, 1) = 1. The left subtree has the remaining nodes, i.e. 3, so that 3 + 1 + 1 (for root) = 5.

Other examples

Here is a table with the results for 𝑛 between 1 and 15:

𝑛	in binary	𝑝	𝑘	𝑝/2 − 1	in right subtree = max(𝑘, 𝑝/2 − 1)	in left subtree
1	0b1	0b1	0b0	0b0	0	0
2	0b10	0b10	0b0	0b0	0	1
3	0b11	0b10	0b1	0b1	1	1
4	0b100	0b100	0b00	0b1	1	2
5	0b101	0b100	0b01	0b1	1	3
6	0b110	0b100	0b10	0b1	2	3
7	0b111	0b100	0b11	0b1	3	3
8	0b1000	0b1000	0b000	0b11	3	4
9	0b1001	0b1000	0b001	0b11	3	5
10	0b1010	0b1000	0b010	0b11	3	6
11	0b1011	0b1000	0b011	0b11	3	7
12	0b1100	0b1000	0b100	0b11	4	7
13	0b1101	0b1000	0b101	0b11	5	7
14	0b1110	0b1000	0b110	0b11	6	7
15	0b1111	0b1000	0b111	0b11	7	7