Depth First Search Algorithm to Delete Even Leaves from Binary Tree

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

Depth First Search Algorithm to Remove Even Leaves from Binary Tree

After we remove the even leaves, we should also continue this process as the intermediate nodes are becoming the new leaves.

Thus, it is ideal to apply the Recursive Depth First Search (DFS) Algorithm on the binary tree, where we are calling the recursively function to remove the leaves in the left and right subtree. And then, if the current node becomes a even leaf node, we will remove it by returning the NULL pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
Tree* removeEvenLeaves(Tree* root) {
    if (!root) return NULL;
    root->left = removeEvenLeaves(root->left);
    root->right = removeEvenLeaves(root->right);
    // if it is a leaf node
    if (root->left == root->right) {
        // if it is even, remove it    
        if ((root->val & 1) == 0) {
            return NULL;
        }
    }
    return root;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
Tree* removeEvenLeaves(Tree* root) {
    if (!root) return NULL;
    root->left = removeEvenLeaves(root->left);
    root->right = removeEvenLeaves(root->right);
    // if it is a leaf node
    if (root->left == root->right) {
        // if it is even, remove it    
        if ((root->val & 1) == 0) {
            return NULL;
        }
    }
    return root;
}

The time complexity is O(N) and the space complexity is also O(N) – due to implicit usage of stack from Recursion. The N is the number of the nodes in the binary tree.

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) —