Teaching Kids Programming – Depth First Search Algorithm to Delete Even Leaves Recursively From Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, repeatedly delete all leaves that have even values. That is, if after deletions, a node becomes a leaf with an even value, it too should be deleted.

Constraints
n ≤ 100,000 where n is the number of nodes in root

Recursive Depth First Search Algorithm to Delete Even Leaves of Binary Tree

We can recursively delete even leaves from both left and right subtrees. And then if current node becomes a new leaf and also it is even – we remove it (return None). Otherwise, we return itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteEvenLeaves(self, root):
        if not root:
            return None
        root.left = self.deleteEvenLeaves(root.left)
        root.right = self.deleteEvenLeaves(root.right)
        if root.left is None and root.right is None:
            if root.val & 1 == 0: # or if root.val % 2 == 0
                return None
        return root

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteEvenLeaves(self, root):
        if not root:
            return None
        root.left = self.deleteEvenLeaves(root.left)
        root.right = self.deleteEvenLeaves(root.right)
        if root.left is None and root.right is None:
            if root.val & 1 == 0: # or if root.val % 2 == 0
                return None
        return root

The time complexity is O(N) where N is the number of the nodes in the binary tree as we need to visit each node exactly once. The space complexity is O(N) due to stack usage implied by the Recursion.

Recursive Algorithm to Prune a Binary Tree

• Teaching Kids Programming – Depth First Search Algorithm to Delete Even Leaves Recursively From Binary Tree
• Depth First Search Algorithm to Delete Even Leaves from Binary Tree
• Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree
• Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —