1

I was trying to find relation between total number of nodes in a complete binary tree and the leaf nodes. Note that a complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.While working it out I got the equation $l=n/2$, where $l$ is the number of leaf nodes and $n$ is the total number of nodes in complete binary tree, if $n$ is even. When $n$ is odd, $l=(n-1)/2$. Now is there a specific way to make these equations into a single equation using floor and ceiling so that it can handle both the cases when n is even or odd. The only way I can think of by plugging the values and observing that it is actually the $\lfloor n/2\rfloor$.

Parcly Taxel
  • 103,344
Amisha Bansal
  • 11
  • Seems the floor of $n/2$ already does both even and odd. Are you looking for a proof? another formula without floor? – coffeemath Jan 12 '19 at 12:27
  • Yes, I am looking for a general approach to find that it narrows down to floor of (n/2) – Amisha Bansal Jan 12 '19 at 12:56
  • Did you find arguments that show if $n$ even then $l=n/2,$ and if $n$ odd then $l=(n-1)/2$ ? Also since tree is binary, every level, if "completely filled", has 2 descendants if it's not a leaf. A leaf has no descendants. One more thing, what does having nodes "as far left as possible" mean, and what has it to do with counting the nodes (how the tree is drawn doesn't affect how many nodes it has) ? – coffeemath Jan 12 '19 at 13:16
  • 1
    @coffeemath "as far left as possible" signifies that the last level may not be completely filled and hence there can be one node at last level which has 1 child . So basically something like this link is also a complete binary tree. – Amisha Bansal Jan 12 '19 at 14:17

0 Answers0