💡 Problem Formulation: A complete binary tree is a type of binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. The challenge is to check if a given binary tree meets this criterion. If we take a binary tree as input, the program should return a boolean indicating whether the tree is complete (True) or not (False).
Method 1: Level Order Traversal Using Queue
This method involves traversing the tree level by level, using a queue to keep track of nodes. Each level is inspected to ensure nodes are positioned correctly. If a null node appears before a non-null node at the same level, the binary tree is not complete. Function signature: is_complete(root).
Here’s an example:
from collections import deque
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def is_complete(root):
if not root:
return True
queue = deque([root])
flag = False
while queue:
node = queue.popleft()
if node:
if flag:
return False
queue.append(node.left)
queue.append(node.right)
else:
flag = True
return True
# Example tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print(is_complete(root))
Output:
True
This code features a function is_complete that takes the root of a binary tree and checks for completeness by performing a level order traversal with a queue. If a null node is found followed by a non-null node, the function returns False indicating the tree is not complete. Otherwise, it returns True.
Method 2: Recursive Depth Counting
A recursive approach that counts the depth of the leftmost and rightmost paths on each subtree. If the depth diverges by more than one, or if the right depth is greater than the left, the tree is incomplete. Function signature: is_complete(root).
Here’s an example:
def is_complete(root, depth=0, leftmost_depth=[0]):
if not root:
if leftmost_depth[0] == 0:
leftmost_depth[0] = depth
return leftmost_depth[0] - 1 <= depth <= leftmost_depth[0]
return is_complete(root.left, depth + 1, leftmost_depth) and is_complete(root.right, depth + 1, leftmost_depth)
# Example tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
print(is_complete(root))
Output:
False
The recursive function is_complete compares the depth of leftmost and rightmost nodes. Initially, it aims to find the depth of the leftmost node, which sets the benchmark for the remaining nodes. It correctly identifies whether the binary tree is complete by checking the position of every node relative to this depth.
Method 3: Node Counting
Count the total number of nodes in the tree and ensure that each node’s position corresponds to a valid position in a complete binary tree using indexing rules. Function signature: is_complete(root).
Here’s an example:
def count_nodes(root):
if root is None:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
def is_complete(root, index=0, node_count=None):
if root is None:
return True
if node_count is None:
node_count = count_nodes(root)
if index >= node_count:
return False
return is_complete(root.left, 2 * index + 1, node_count) and is_complete(root.right, 2 * index + 2, node_count)
# Example tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
print(is_complete(root))
Output:
True
This method uses the function count_nodes to find the total number of nodes. The function is_complete makes sure every node’s index is in the appropriate position that it would be in a complete binary tree, based on the total count of nodes.
Method 4: Iterative Depth and Completeness Check
This method leverages an iterative deepening approach, verifying depth level and node completeness at each iteration. It combines aspects of level order traversal and node counting. Function signature: is_complete(root).
Here’s an example:
def is_complete(root):
if not root:
return True
queue = [(root, 0)]
expected_index = 0
while queue:
node, index = queue.pop(0)
if index != expected_index:
return False
expected_index += 1
if node.left:
queue.append((node.left, index * 2 + 1))
if node.right:
queue.append((node.right, index * 2 + 2))
return True
# Example tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(7)
print(is_complete(root))
Output:
False
An iterative approach, is_complete traverses the tree while assigning consecutive indices to the nodes. If a node’s index does not match the expected index, we infer the tree is not complete, and the function returns False.
Bonus One-Liner Method 5: Pythonic BFS with Generator Expression
A compact one-liner utilizing a breadth-first search (BFS) and a generator expression. This method uses advanced Pythonic constructs to achieve the same check in a single statement. Function signature: is_complete(root).
Here’s an example:
is_complete = lambda root: not any(child for node in (None, root) if node for child in (node.left, node.right)) # Example tree root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print(is_complete(root))
Output:
True
This concise lambda function iterates over the tree using a BFS pattern in a generator expression, checking if any child node is None after an earlier None has been found, thereby determining the completeness of the tree.
Summary/Discussion
- Method 1: Level Order Traversal Using Queue. Straightforward and intuitive. May use more memory for the queue with large trees.
- Method 2: Recursive Depth Counting. Simple with less space complexity. Recursive depth limit may be an issue for very deep trees.
- Method 3: Node Counting. Very accurate as it relates to the very definition of a complete tree. Requires multiple passes to count nodes and then check positions.
- Method 4: Iterative Depth and Completeness Check. Offers a good balance between the other methods but assumes consecutive indexing matches complete tree structure.
- Bonus Method 5: Pythonic BFS with Generator Expression. Compact, elegant, and efficient for smaller trees. May be harder to read and understand for beginners, and not the most debug-friendly.