More on Complete Binary Trees

In this lesson, we are going to discuss what Complete Binary Trees are and how elements are inserted into them.

Introduction

We touched upon complete binary trees in the last lesson, but here are some more detailed properties of them.

  • All the levels are completely filled except possibly the last one.
  • Nodes at the last level are as far left as possible.
  • The total number of nodes in a complete binary tree of height “h” are: 2hnodes2h+112^h \leq nodes \leq 2^{h+1}-1. This is again based on the Geometric Series formula: 20+21+23+24+...+2r=2r+112^0+2^1+2^3+2^4+...+2^r = 2^{r+1}-1.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.