For a complete binary tree with n nodes, how many nodes are leaf nodes?

tree nodes binary-search-tree
Amit Jain picture Amit Jain · Nov 9, 2014 · Viewed 23.1k times · Source

One of the answers in our powerpoint says it is n/2 leaves, but I am seeing another answer which says (n+1)/2. I was wondering which one is correct if any, and why?

Answer

Robert Bain picture Robert Bain · Nov 9, 2014

In the simplest case a binary tree with a root node, a left and a right has 3 nodes, two of which are leaf nodes. It's (n+1)/2.

Related questions

What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More
Is the root node an internal node?

So I've looked around the web and a couple of questions here in stackoverflow here are the definition: Generally, an internal node is any node that is not a leaf (a node with no children) Non-leaf/Non-terminal/Internal node – has …

Read More
Get all child, grandchild etc nodes under parent using php with mysql query results

I've been trying to figure this out but I haven't gotten anywhere.Hopefully someone can come to my rescue. My problem is I'm using adjacency list data model to produce my hierarchy data in mysql.I can retrieve the table (…

Read More