The half-full node

MediumProgramming & DSA~4m

A complete binary tree has every level full except possibly the last, which is filled left-to-right. Stored in a $0$ -indexed array of $100$ nodes (node $i$ has children at $2i+1$ and $2i+2$ ), how many of its nodes have exactly one child (as opposed to two children or none)?

Show hints (2)+

A one-child node needs its left-child index in range but its right-child index out of range: $2i+1 = N-1$ .
That equation has an integer solution only when $N$ is even - how many solutions, and is $100$ even?

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Hedge Fund Quant, Prop Trading

The half-full node

Answer

Related questions