|
This post is completed by 1 user
|
Add to List |
443. Check the completeness of given binary tree | Set 2 - Using Level Order Traversal
Objective: Given a binary tree, write an algorithm to determine whether the tree is complete or not using Level order traversal.
Earlier we had solved this problem by counting the number of nodes in the tree. (Read - Check the completeness of given binary tree | Set 1 - Using Node Count. In this article, we will solve it using level order traversal.
Before we proceed, If you are reading about the completeness of binary tree for the first time then let's first understand it with some examples.
Complete Binary Tree: A binary tree is complete if all levels are completely full except the last level. The last level may or may not be full and nodes should be on the left side.
Example:
Below is an example of a special case where the tree is full expect the last level and in the last level, the nodes have priority to be one the left side if the last level is not full. See the example below
Approach: Level Order Traversal
(Read about level order traversal here)
- Do the level order traversal from left to right.
- Once a null node is found, ideally there should not be any node present after that if the tree is complete. If that's the case return true.
- So if a node is found which is not null after a null node that means the tree is not complete, return false.
- See the image below for more understanding.
Output:
Given Binary Tree is a Binary Tree: false Given Binary Tree is a Binary Tree: true