|
Be the first user to complete this post
|
Add to List |
431. Check the completeness of given binary tree | Set 1 - Using Node Count
Objective: Given a binary tree, write an algorithm to determine whether the tree is complete or not.
Complete Binary Tree: A binary tree T with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.
Example:
Below is an example of a special case where the tree is full except the last level. Even 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: Use Nodes count
- Count the number of nodes in the tree.
- Now start assigning indexes to tree nodes starting from the root (index 0) and at each level increase the index from left to right.
- If at any node assigned index is greater than the node count, that means the tree is not constructed in the right manner to be called a complete tree, return false.
- If all the tree nodes are successfully assigned indexes and at each node, the index is less than node count then it means the tree is complete, return true.
- See the image below for more understanding.
Output:
Given Binary Tree is a Binary Tree: false Given Binary Tree is a Binary Tree: true
Reference: this