# 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.