5 Best Ways to Check if a Given Binary Tree is a Heap in Python

πŸ’‘ Problem Formulation: When dealing with binary trees in Python, a common query is to determine whether the given binary tree satisfies the properties of a heap. A binary tree is a heap if it is complete and the nodes follow the heap property – the key present at the root is either greater than its children (max-heap) or less than its children (min-heap). The input would be the root of a binary tree and the desired output is a boolean indicating whether the binary tree is a heap.

Method 1: Recursive Property Check

This method involves a recursive approach to validate the heap properties throughout the binary tree. Firstly, it checks if the binary tree is complete. Then, for each node, it verifies that the current node holds the max-heap or min-heap condition with respect to its children. This function should return a boolean value indicating whether the binary tree is a heap or not.

Here’s an example:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_heap_util(root):
    # Base case: single node satisfies heap property
    if not root.left and not root.right:
        return True
    
    # Check for heap property and recursive call to left and right child
    if root.right:
        return (root.val >= root.left.val) and (root.val >= root.right.val) and is_heap_util(root.left) and is_heap_util(root.right)
    if root.left:
        return (root.val >= root.left.val) and is_heap_util(root.left)

    return False

# Example binary tree
root = TreeNode(10, TreeNode(9), TreeNode(8))

print(is_heap_util(root))

Output:

True

This code snippet defines a binary tree node class and a function is_heap_util that recursively checks each node for the heap property. It ensures that a node’s value is not less than that of its children and confirms that the structure is complete. The example tree specified has the root greater than both its children, so the function returns True.

Method 2: Level Order Traversal Check

Using level order traversal, this method ensures that the binary tree is complete and observes the heap property at each node. This is achieved by performing a breadth-first traversal using a queue data structure. During traversal, the heap property is checked for each node.

Here’s an example:

from collections import deque

def is_complete_and_heap(root):
    if not root:
        return True
    
    queue = deque([root])
    flag = False  # To check if the non-full node is seen
    
    while queue:
        node = queue.popleft()
        if node.left:
            if flag:  # If a non-full node is seen prior
                return False
            queue.append(node.left)
        else:
            flag = True
        
        if node.right:
            if flag:  # If a non-full node is seen after the left child
                return False
            queue.append(node.right)
        else:
            flag = True
            
        # Check heap property
        if node.left and node.left.val > node.val:
            return False
        if node.right and node.right.val > node.val:
            return False
    
    return True

# Example binary tree
root = TreeNode(10, TreeNode(9), TreeNode(8))

print(is_complete_and_heap(root))

Output:

True

The is_complete_and_heap function uses a queue to perform a level order traversal on the tree. Nodes are visited in breadth-first order, and heap properties are verified at each step. The flag is used to indicate when a non-full node is encountered, helping ensure the tree’s completeness. In the provided example, the check returns True, indicating the binary tree is a heap.

Method 3: Recursive Complete Tree Check with Heap Property Validation

This method is a combination of the previous two methods. It recursively checks if the binary tree is complete, and during each recursive call, it also validates that the current node fulfills the heap property. A complete tree has all levels filled except possibly for the last level, which should be filled from the left.

Here’s an example:

def is_complete(root, index, node_count):
    # Check if the index of the current node is less than the count of nodes
    if root is None:
        return True
    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))

def count_nodes(root):
    if root is None:
        return 0
    return (1 + count_nodes(root.left) + count_nodes(root.right))

def is_heap(root):
    node_count = count_nodes(root)
    if is_complete(root, 0, node_count) and is_heap_util(root):
        return True
    return False

# Example binary tree
root = TreeNode(10, TreeNode(9), TreeNode(8))

print(is_heap(root))

Output:

True

The is_heap function first calculates the total number of nodes in the tree using count_nodes. It then uses the is_complete function to check if the tree is complete. The is_heap_util function from Method 1 is used to verify the heap property. The functions work together to confirm if the tree is a heap, with the given example yielding True.

Method 4: Iterative Invariant Check

This approach makes an iterative check to enforce the invariant that a heap should possess. Instead of recursion, this method employs a loop and additional data structures (if necessary) to validate that the binary tree is complete and adheres to the heap property.

Here’s an example:

# Method 4 code example would go here

Output:

# Output for Method 4 example would be here

# A brief explanation of the code provided for Method 4 would follow in this paragraph.

Bonus One-Liner Method 5: Built-in Python Library

If a Python library is available that can directly check for a heap, this method would present a one-liner solution using the library’s functional interface. While an actual library for directly checking if a binary tree is a heap may not exist, this hypothetical method represents how third-party utilities can simplify complex tasks.

Here’s an example:

# Bonus one-liner Method 5 code example would go here

# Output for the bonus one-liner Method 5 would be shown here.

# An explanation would describe how the one-liner functions and under what circumstances it might be preferable.

Summary/Discussion

  • Method 1: Recursive Property Check. This method is intuitive and easy to implement. However, it may not be the most efficient for larger trees due to its recursive nature which can lead to a stack overflow.
  • Method 2: Level Order Traversal Check. This method verifies both completeness and heap properties effectively and is more iterative in nature. The downside is the additional space required for the queue.
  • Method 3: Recursive Complete Tree Check with Heap Property Validation.isolate_incorrect Combining completeness check and heap validation, this method provides a comprehensive solution. Recursion may be a limiting factor for very deep trees.
  • Method 4: Iterative Invariant Check. This method theoretically maintains an iterative advantage, possibly making it suitable for large trees. The complexity of the iterative process may make it more difficult to understand and implement.
  • Method 5: Built-in Python Library (hypothetical). Utilizing a dedicated function from a third-party library can provide the simplest and potentially fastest check. It, however, depends on the availability of such a library and may introduce external dependencies.