Solution For Check Completeness Of A Binary Tree
Problem Statement:
Given the root of a binary tree, determine if it is a complete binary tree.
A binary tree is complete if 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:
Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level except the last is full, and the last level has all nodes as far left as possible.
Solution:
To determine if a binary tree is complete, we need to check if the nodes are following the rule of having nodes in last level added from left to right without leaving any gaps. Let’s define few terms for better understanding-
height = ht
Nodes in a complete tree = 2^ht – 1
Nodes in the last level = k (in a non-empty tree)
In a complete tree, the minimum number of nodes in the last level is “1” and the maximum is 2^k-1.
The easiest way to check this is to sweep across the tree from left to right and check if any gap exists in between. Once we find a gap, it should be the last level, and all the nodes that come next should be null pointers. If we find any node after the null pointers, we can declare that the tree is not complete. Otherwise, the tree will be complete.
Algorithm:
- Calculating the height or maximum levels of the tree.
- Perform a level order traversal, and for each node after the first null child:
a. If flag is true, return False, as we’ve already skipped blank spots
b. Set flag to true if one null child is found - If we’ve never returned False on a node w/ 1 non-null child, return True.
Code implementation:
In order to implement the above algorithm, we will write a recursive function in Python:
def isCompleteTree(root: TreeNode) -> bool:
def check(root, i, n):
if not root:
return True
if i >= n:
return False
return (check(root.left,2*i+1,n) and check(root.right,2*i+2,n))
# Calculating the number of nodes and height in the tree
count = 0
height = 0
nodeCount = [0]
q = [root]
while q:
temp = q.pop(0)
count += 1
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
if not q:
nodeCount.append(count)
if count == 2**height:
height += 1
count = 0
n = nodeCount[-1]
# Perform a level order traversal and check for gaps
return check(root,0,n)
Time Complexity:
In the worst case, this algorithm will traverse the complete binary tree (O(n)nodes) once. Therefore, the time complexity of this algorithm is O(n).
Space Complexity:
The space required for the queue is O(n), which is the maximum size of the queue while traversing the tree.
Summary:
In this problem, we have learned how to determine whether a binary tree is a complete binary tree or not. We identified that a complete binary tree has no gaps in the last level, and we have designed an algorithm that uses a level order traversal to check for gaps and verify whether a binary tree is complete. The time and space complexity of our algorithm is O(n), where n is the number of nodes in the binary tree.
Step by Step Implementation For Check Completeness Of A Binary Tree
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isCompleteTree(TreeNode root) { // Base case if (root == null) { return true; } // Create a queue and add the root node Queuequeue = new LinkedList<>(); queue.add(root); // Variable to keep track of whether we have seen a non-full node boolean seenNonFull = false; // Iterate over the queue until it's empty while (!queue.isEmpty()) { // Get the node at the front of the queue TreeNode curr = queue.remove(); // If we have seen a non-full node, we should only see null nodes from here on out if (seenNonFull) { if (curr.left != null || curr.right != null) { return false; } } // Otherwise, we need to check if the current node is non-full else { // Case 1: Current node is a leaf node (has no children) if (curr.left == null && curr.right == null) { continue; } // Case 2: Current node has only a left child else if (curr.left != null && curr.right == null) { queue.add(curr.left); seenNonFull = true; } // Case 3: Current node has only a right child else if (curr.left == null && curr.right != null) { return false; } // Case 4: Current node has both left and right children else { queue.add(curr.left); queue.add(curr.right); } } } // If we get to this point, that means we have successfully traversed the tree // and all nodes are either full or we have only seen null nodes after encountering // a non-full node. Therefore, the tree is complete. return true; } }
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isCompleteTree(self, root): """ :type root: TreeNode :rtype: bool """ # if the tree is empty, return true if not root: return True # create a queue and add the root node queue = [root] # set a flag to track if we have seen a non-full node seen_nonfull = False # while the queue is not empty while queue: # get the next node from the queue node = queue.pop(0) # if we have seen a non-full node, and the current node is not a leaf # (i.e. it has at least one child), then the tree is not complete if seen_nonfull and (node.left or node.right): return False # if the current node has a left child, add it to the queue if node.left: queue.append(node.left) # otherwise, we have seen a non-full node else: seen_nonfull = True # if the current node has a right child, add it to the queue if node.right: queue.append(node.right) # otherwise, we have seen a non-full node else: seen_nonfull = True # if we reach this point, the tree is complete return True
// given a binary tree, check if it is a complete binary tree or not function isCompleteBinaryTree(root) { // if the tree is empty, it is complete if (!root) return true; // get the height of the tree let height = getHeight(root); // get the number of nodes in the tree let nodeCount = getNodeCount(root); // if the node count is equal to 2^height - 1, it is a complete binary tree return nodeCount == Math.pow(2, height) - 1; } // get the height of the tree function getHeight(root) { // if the tree is empty, the height is 0 if (!root) return 0; // recursively get the height of the left and right subtrees let leftHeight = getHeight(root.left); let rightHeight = getHeight(root.right); // return the height of the tree (the larger of the two subtrees + 1) return Math.max(leftHeight, rightHeight) + 1; } // get the number of nodes in the tree function getNodeCount(root) { // if the tree is empty, the node count is 0 if (!root) return 0; // recursively get the node count of the left and right subtrees let leftCount = getNodeCount(root.left); let rightCount = getNodeCount(root.right); // return the node count of the tree (the sum of the left and right subtrees) return leftCount + rightCount + 1; }
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isCompleteTree(TreeNode* root) { // Base case if (root == nullptr) { return true; } // Create an empty queue queueq; // Enqueue root node q.push(root); // Iterate while there are nodes in the queue while (!q.empty()) { // Dequeue a node from the queue TreeNode* curr = q.front(); q.pop(); // If this node is NULL, then we have encountered // a leaf node. Since the tree is supposed to be // complete, we should not encounter any more // nodes after this. if (curr == nullptr) { break; } // Enqueue the left and right child nodes of // the current node q.push(curr->left); q.push(curr->right); } // Now, we check if the queue is empty. If it is // empty, then the tree is complete. If not, then // the tree is not complete. return q.empty(); } };
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public bool IsCompleteTree(TreeNode root) { // Base case if (root == null) return true; // Create an empty queue Queuequeue = new Queue (); // Enqueue Root queue.Enqueue(root); // While there are nodes in the queue while (queue.Count != 0) { // Dequeue a node from the queue TreeNode node = queue.Dequeue(); /* If this is the last node of the level, enqueue a marker for level ending. */ if (node.left == null && node.right != null) return false; if (node.right != null) queue.Enqueue(node.right); if (node.left != null) queue.Enqueue(node.left); /* If this a non-full node, make sure no node exists after it */ else if (node.left == null && node.right == null) { if (queue.Count != 0) return false; } } // The tree is complete return true; } }