Solved! Leetcode 958. Check Completeness of a Binary Tree

Problem description

source: https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/

Check Completeness of a Binary Tree

Given the 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. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> next = new LinkedList<>();
        next.add(root);
        TreeNode prev = new TreeNode(-1);
        while(!next.isEmpty()){
            int size = next.size();
            for(int i=0;i<size;i++){
                TreeNode node = next.poll();
                //if the prev node is null and the current node is not null, then we have a situation where left child is null and right child is not null
                if(prev==null && node!=null){
                    return false;
                }
                prev = node;
                if(node!=null){
                    next.add(node.left);
                    next.add(node.right);
                }
            }
        }
        return true;
    }
}

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

class Solution {

public boolean isCompleteTree(TreeNode root) {

Queue<TreeNode> next = new LinkedList<>();

next.add(root);

TreeNode prev = new TreeNode(-1);

while(!next.isEmpty()){

int size = next.size();

for(int i=0;i<size;i++){

TreeNode node = next.poll();

//if the prev node is null and the current node is not null, then we have a situation where left child is null and right child is not null

if(prev==null && node!=null){

return false;

}

prev = node;

if(node!=null){

next.add(node.left);

next.add(node.right);

}

return true;

}

Time Complexity

O(n), where n is the number of nodes in a tree

Space Complexity

O(n), where n is the number of nodes in a tree

Python

Approach 1

By numbering the nodes on level and checking if any number in sequence is missing

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        queue = [(root, 1, 0)]  # storing (node-pointer, index, node-level)
        
        def bfs(q):
            lvl_count = defaultdict(int)
            curr_level = 0
            while q:
                #print(q)
                node, ind, lvl = q.pop(0)
                lvl_count[lvl] += 1
                if curr_level != lvl:
                    # new level started, check if previous level had all nodes present
                    if lvl_count[curr_level] != math.pow(2, curr_level):
                        return False
                    curr_level = lvl
                
                if node.left == None and node.right == None:
                    continue
                if node.left == None and node.right:
                    return False
                
                left_child_ind = ind + (ind - 1)
                right_child_ind = left_child_ind + 1    
                if left_child_ind > 1 and (not q or q[-1][1] + 1 != left_child_ind):
                    return False
                child_lvl = lvl + 1
                q.append((node.left, left_child_ind, child_lvl))
                if node.right:
                    q.append((node.right, right_child_ind, child_lvl))
            return True
        return bfs(queue)

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def isCompleteTree(self, root: Optional[TreeNode]) -> bool:

queue = [(root, 1, 0)] # storing (node-pointer, index, node-level)

def bfs(q):

lvl_count = defaultdict(int)

curr_level = 0

while q:

#print(q)

node, ind, lvl = q.pop(0)

lvl_count[lvl] += 1

if curr_level != lvl:

# new level started, check if previous level had all nodes present

if lvl_count[curr_level] != math.pow(2, curr_level):

return False

curr_level = lvl

if node.left == None and node.right == None:

continue

if node.left == None and node.right:

return False

left_child_ind = ind + (ind - 1)

right_child_ind = left_child_ind + 1

if left_child_ind > 1 and (not q or q[-1][1] + 1 != left_child_ind):

return False

child_lvl = lvl + 1

q.append((node.left, left_child_ind, child_lvl))

if node.right:

q.append((node.right, right_child_ind, child_lvl))

return True

return bfs(queue)

Approach 2

Null node/ pointer checks

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        q = [root]  # storing node-pointer
        null_node_found = False
        while q:
            node = q.pop(0)
            if node == None:
                null_node_found = True
                continue
            if null_node_found:
                return False
            q.append(node.left)
            q.append(node.right)
            
        return True

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def isCompleteTree(self, root: Optional[TreeNode]) -> bool:

q = [root] # storing node-pointer

null_node_found = False

while q:

node = q.pop(0)

if node == None:

null_node_found = True

continue

if null_node_found:

return False

q.append(node.left)

q.append(node.right)

return True

Time and Space complexities are same as those in Java solution

Rate this post

Coddicted

Solved! Leetcode 958. Check Completeness of a Binary Tree

Table of Contents

Problem description

Check Completeness of a Binary Tree

Java

Time Complexity

Space Complexity

Python

Approach 1

Approach 2

Leave a Reply Cancel Reply