Identify Complete Binary Tree — Leetcode 958

Hello, Myself Gauri wankhade,
Software Developer, Bangalore, India

In this article we will be solving leetcode problem for below problem statement.

⚡Problem Statement:-

We have given root of a binary tree, determine if it is a complete binary tree.

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.

Example 1:

Input: root = [1, 2, 3, 4, 5, 6]
Output: true
Explanation: Every level before the last is full.

Example 2:

Input: root = [1, 2, 3, 4, 5, null, 7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• 1 <= Node.val <= 1000.

⚡Thinking process:-

In order to consider given tree as a binary tree we need to check two conditions —

• All the levels of tree are completely filled up, except for the last level.
• Last level of tree is filled up from left

⚡Solution:-

Step 1:- Since, we are trying to access each node in level-order, BFS is the suitable approach.

Step 2:- We need an identifier to check if there exists a Null node in any level. Once we capture a node with Null value, set the value of identifier.

Step 3:- If there exists a not-null node after identifier is set, binary tree is not complete binary tree.

⚡Code:-

⚡Complexity Analysis:-

• Time complexity:- O(N) where N is a number of nodes in tree
• Space complexity:- O(N) as we have used Queue for storing each node.

Please do share and like if you find the article useful. Follow me on medium Gauri wankhade and on Twitter at gauri_infj.

Thanks!!!

Happy Learning…