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: trueExplanation: Every level before the last is full.
Example 2:
Input: root = [1, 2, 3, 4, 5, null, 7]
Output: falseExplanation: 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…