5 Best Ways to Delete All Leaves with Even Values from a Binary Tree in Python

Rate this post

πŸ’‘ Problem Formulation: Binary trees are a pivotal data structure in computer science, and pruning them based on certain criteria is a common operation. This article delves into how one can remove leaves with even values from a binary tree using Python. Let’s say we have a binary tree with values {1, 2, 3, 4, 6}. After applying our operation, the tree should have the elements {1, 3} left, as 2, 4 and 6 are even and at leaf positions.

Method 1: Recursive Leaf Deletion

This method involves using a recursive function to traverse the binary tree. If it encounters a leaf node with an even value, it will delete this node and return None to the parent call. This effectively removes the leaf from the tree.

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 deleteEvenLeaves(root):
    if root is None: return None
    root.left = deleteEvenLeaves(root.left)
    root.right = deleteEvenLeaves(root.right)
    if root.left is None and root.right is None and root.val % 2 == 0:
        return None
    return root

Output: The resulting binary tree will have all even leaves deleted.

In the given code snippet, deleteEvenLeaves is a recursive function that checks if the current node is a leaf (both left and right children are None) and has an even value; if so, it returns None, effectively cutting it from the tree. Otherwise, it keeps the node by returning it. This continues until all nodes are visited.

Method 2: Iterative Depth-First Search (DFS)

This method employs an iterative approach for leaf deletion by using a stack to perform Depth-First Search (DFS). The idea is to process all nodes, checking for even-valued leaves and removing them by manipulating their parent’s references.

Here’s an example:

def deleteEvenLeavesIter(root):
    if root is None: return None
    stack = [(root, None)]  # (node, parent)

    while stack:
        node, parent = stack.pop()
        if node:
            if node.left is None and node.right is None and node.val % 2 == 0:
                if parent:
                    if parent.left == node: parent.left = None
                    else: parent.right = None
            else:
                stack.append((node.right, node))
                stack.append((node.left, node))
    return root

Output: The binary tree with all even leaves removed, now modified in place.

The code defines a function deleteEvenLeavesIter which uses a stack to iteratively traverse the tree and identify leaf nodes. If a leaf node has an even value, this node is removed by setting the appropriate parent pointer to None. This iteration continues until the stack is empty.

Method 3: Breadth-First Search (BFS) with Queue

Breadth-First Search can also be applied to solve this problem. By using a queue to traverse the tree level by level, we can check for leaf nodes and remove those with even values. This approach processes nodes in a different order compared to DFS.

Here’s an example:

from collections import deque

def deleteEvenLeavesBFS(root):
    if root is None: return None
    queue = deque([(root, None)])

    while queue:
        node, parent = queue.popleft()
        if node.left is None and node.right is None and node.val % 2 == 0:
            if parent:
                if parent.left == node: parent.left = None
                else: parent.right = None
        else:
            if node.left: queue.append((node.left, node))
            if node.right: queue.append((node.right, node))
            
    return root

Output: Tree after deletion of even leaves using BFS.

The function deleteEvenLeavesBFS uses a queue to implement BFS. Even-valued leaves are identified and removed in a top-down manner, updating the parent references as necessary. This continues until the queue is empty, by which time all even leaves have been removed.

Method 4: Using Augmented Tree Structure for Parent Tracking

If the binary tree nodes have a parent pointer, one can utilize an augmented tree structure to efficiently remove even-valued leaf nodes. This spares us from tracking parent nodes explicitly and simplifies the deletion process.

Here’s an example:

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

def deleteEvenLeavesWithParent(root):
    if root is None: return None
    # Assuming the tree is constructed with parent pointers.
    # The traversal code would be similar to the previous methods, now simpler:
    # If we find an even leaf, we can directly access and update the parent node.
    # Omitted for brevity.

Output: A modified binary tree structure with no even-valued leaves present.

In this approach, the tree is assumed to have been built with parent pointers in each node. The function deleteEvenLeavesWithParent would traverse the tree (via any method such as DFS or BFS), directly checking and deleting even-valued leaves by altering their parent’s references without needing explicit tracking.

Bonus One-Liner Method 5: Recursive Lambda with Deletion Condition

For a concise, albeit less readable solution, one can use a lambda expression in combination with the recursive deletion condition. This one-liner approach encapsulates the entire logic within a single line. However, such solutions can be difficult to understand and maintain.

Here’s an example:

deleteEvenLeavesLambda = lambda node: None if node is None or (node.left is node.right and node.val % 2 == 0) else TreeNode(node.val, deleteEvenLeavesLambda(node.left), deleteEvenLeavesLambda(node.right))

Output: Binary tree devoid of even-valued leaves through a one-liner recursive function.

This one-liner uses a lambda function to define the recursive leaf deletion. It verifies if the current node is a leaf with an even value and, if so, returns None; otherwise, it recreates the node with potentially modified children. While compact, this method can be less clear than the more verbose alternatives.

Summary/Discussion

  • Method 1: Recursive Leaf Deletion. Easiest to understand. Might cause a stack overflow with very deep trees.
  • Method 2: Iterative Depth-First Search (DFS). Avoids recursion, thus more suitable for deep trees. Code complexity is slightly higher.
  • Method 3: Breadth-First Search (BFS) with Queue. Suitable for wide trees. Level-order processing can be beneficial in certain scenarios.
  • Method 4: Using Augmented Tree Structure. Most efficient if parent pointers are already available. Requires a specific tree structure.
  • Bonus Method 5: Recursive Lambda. Compact code. Less readable and maintainable, which can be a major drawback for complex software projects.