# Complete Binary Tree

In this article, we are going to see **what Complete Binary Tree is and what are the properties of a complete binary tree and differences between Full Binary Tree and Complete Binary Tree**. Also, in the end, we have added a Program to compute the number of nodes in a complete binary search efficiently using its properties.

Submitted by Radib Kar, on July 31, 2020

**Prerequisite:**

In the last article we talked about **full binary tree**, and **complete binary tree** is another classification of binary tree. As per Defined in Wikipedia:

In a **complete binary tree** every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. A complete Binary Tree can have between *1* and *2h* nodes inclusive at the last level *h*.

So, the properties of **complete Binary tree** are:

- All levels are filled up except the last level
- The nodes at the last levels are as far left as possible

## Examples of Complete Binary Tree

Below are a few examples where we have showed which one is Full Binary Tree and which is Complete Binary Tree. There are cases also where a binary tree is both full and complete and also there are cases where a binary tree is neither a full binary tree nor a complete binary tree.

### 1) Neither Complete Binary Tree Nor Full Binary Tree

**Figure 1: Neither Full nor complete binary tree**

The above binary tree is neither a complete Tree nor a Full Binary Tree.

It's not a Full Binary Tree because the node with value 3 has only one children. The tree is not complete because the node at the last level is not as left as far possible.

### 2) Complete Binary Tree but not Full Binary Tree

**Figure 2: Complete Binary Tree but not Full Binary Tree**

The above Tree is not a Full Binary Tree because the node with value 2 has only one child. But the above tree is complete as the node at the last level is as left as far possible and other levels are completely filled.

### 3) Full Binary Tree but not Complete Binary tree

**Figure 3: Full Binary Tree but Not complete binary tree**

The above tree is a Full binary tree has each node has either two or zero children. But it's not a complete binary tree as the nodes at the last level is not as much left as far possible.

### 4) Both Full Binary Tree and Complete Binary Tree

**Figure 4: Both Full & Complete Binary Tree**

The above tree is both Complete and Full binary tree as it follows both the protocols. Like, all nodes have either zero or two children which makes it a full binary tree & the last level has nodes as left as far possible, and all the previous levels are completed which makes it a complete binary Tree.

Hope, the above examples clears all confusion b/w complete and full binary tree and also helps to distinguish between them.

## Application of complete Binary Tree

We have a very vast application of complete binary tree which is **heap**

## Properties of Complete Binary tree and counting number of nodes efficiently

As per definition the complete binary tree has two properties:

- All the levels are completed except the last levels
- The last level has leaf nodes as left as far possible.

So, we can count total number of nodes using these two properties:

Say, total number of nodes is *n*

And the height of the complete binary tree is:** h**

Then it's guaranteed that all levels up to height h-1 is completed which means has **2 ^{h}-1 number of nodes up to the last level. **At the last level say there r k number of nodes which are as left as much possible. So, we total no of nodes n= k+

**2**

^{h}-1**So, we need to find two things:**

- Height of the tree
- Number of nodes at the last level

Height of the tree can be found in O(Log_{2}n) time and we can find **k also in logarithmic time complexity **using the fact that all the nodes at last level lies as left as far possible.

**The algorithm is like below:**

- If root is NULL return 0
- Compute the height of the tree, h.
- If height is 1 then return 1( Only root is there)
- As we discussed earlier that all the levels except the last one completed and has 2
^{h}-1 number of nodes. We can compute that in constant time as we already know. Now, we have to calculate number of nodes at the last level,*h*. The number of nodes in the last level can be anything between 1 to 2*k*^{h}. Now to find out exact number of nodes, we perform the binary search like the below implementation by the node index to check how many nodes are in the last level. Say the function iswhich takes number of nodes we expect to be at last level, height of tree and returns true or false. It returns true if the last level has same more nodes that we expected and returns false if the last node has less number of notes than expected. We can find this also in logarithmic time as shown as in the implementation*is_exists***(It's possible because of the fact that all nodes are as left as far possible in the last level for complete binary tree)**. So overall complexity for finding number of nodes is**O(logn)*O(logn)**

So over all time complexity is* O(logn)* (to find height and number of nodes in all levels except the last one)+

**to find number of nodes in the last level**

*O(logn)*^{2}(

*)***C++ Implementation:**

#include <bits/stdc++.h> using namespace std; class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int v) { val = v; left = NULL; right = NULL; } }; bool is_exists(TreeNode* root, int h, int no_of_nodes) { TreeNode* cur = root; int left = 0, right = pow(2, h) - 1; //loop runs for h=O(logn) time //binary search to find the no_of_nodes th //node exist or not for (int i = 0; i < h; ++i) { int mid = left + (right - left) / 2; if (no_of_nodes <= mid) { cur = cur->left; right = mid; } else { cur = cur->right; left = mid + 1; } } //if no_of_nodes at last level exists then //cur will point to that no_of_nodes th node //else NULL return cur != NULL; } //since it's a complete tree we can //traverse towards the left child always //since the last level nodes will be as //left as far possible int height(TreeNode* root) { if (!root) return 0; TreeNode* cur = root; int count = 0; while (cur) { count++; cur = cur->left; } return count; } //calculate number of nodes in the //complete tree efficiently int countNodes(TreeNode* root) { if (!root) return 0; if (!root->left && !root->right) return 1; int h = height(root) - 1; //number of nodes except the last level //is calculated as follow int no_of_nodes_except_last_level = pow(2, h) - 1; //number of possible nodes at the last level int left = 1, right = no_of_nodes_except_last_level; int last_level_nodes; //do binary search to check if predicted number //of node exists or not while (left <= right) { int mid = left + (right - left) / 2; //finds if last level has mid number of //nodes or not if (is_exists(root, h, mid)) { left = mid + 1; } else right = mid - 1; } last_level_nodes = left; return no_of_nodes_except_last_level + last_level_nodes; } int main() { cout << "Tree which is both complete and full in example 4\n"; TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); cout << "Number of nodes in this tree: " << countNodes(root) << endl; return 0; }

**Output:**

Tree which is both complete and full in example 4 Number of nodes in this tree: 5

**Relevant post:** Count Number of Nodes in a complete binary tree

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions