Posted on by Kalkicode
Code Binary Tree

Check if given binary tree is complete binary tree or not

A complete binary tree is a binary tree in which all levels except the last are completely filled, and all nodes in the last level are left-justified. In other words, a complete binary tree is a binary tree where every level is completely filled, except possibly the last level, and all nodes are as far left as possible.

Complete Binary Tree Example

To check if a given binary tree is a complete binary tree or not, we can follow the below steps:

  1. Perform a level order traversal of the binary tree.
  2. For each node encountered during the traversal, mark its left and right children as present and enqueue them.
  3. If we encounter a null node, mark its left and right children as absent.
  4. After the traversal, if we encounter a node whose left child is marked as absent, but the right child is present, or if we encounter a node whose left child is present, but the right child is absent or marked as absent, then the tree is not a complete binary tree.

If we do not encounter such a node during the traversal, then the given binary tree is a complete binary tree.

Code Example

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment