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

Here are some more detailed properties of complete binary trees.

  • 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, nn, 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.