Delete Leaves With a Given Value - Practice Coding Problems

Delete Leaves With a Given Value - Problem

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note: Once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted. You need to continue doing this until you cannot delete any more nodes.

Input & Output

Example 1 — Basic Leaf Deletion

$ Input: root = [1,2,3,2,null,2,4], target = 2

› Output: [1,null,3,null,4]

💡 Note: First remove leaf nodes with value 2, which are at positions. After removal, some nodes become new leaves with value 2, so continue deleting until no target leaves remain.

Example 2 — Cascade Deletion

$ Input: root = [1,3,3,3,2], target = 3

› Output: [1,3,null,null,2]

💡 Note: Remove leaf node 3, then the parent 3 becomes a leaf and gets removed too. Continue until no more target leaves exist.

Example 3 — Complete Deletion

$ Input: root = [1,1,1], target = 1

› Output: []

💡 Note: All leaf nodes are 1, after removing them, root becomes leaf with value 1, so it gets deleted too. Final tree is empty.

Constraints

1 ≤ Number of nodes ≤ 3000
1 ≤ Node.val ≤ 1000
1 ≤ target ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with target value leaf nodes

Remove Leaves

Delete leaf nodes matching target value

Cascade Effect

New leaves may need deletion too

Key Takeaway

🎯 Key Insight: Use post-order DFS to process children before parents, enabling single-pass cascade deletion

Asked in

a Amazon 15 f Facebook 12 M Microsoft 8

The key insight is using post-order DFS traversal to process children before parents, allowing single-pass deletion of target leaf nodes. Best approach is Post-order DFS with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Multiple Pass Traversal	O(n²)	O(h)	Repeatedly traverse tree and remove target leaf nodes until no changes occur
Post-order DFS (Optimal)	O(n)	O(h)	Use post-order traversal to process children before parents in single pass

Multiple Pass Traversal — Algorithm Steps

Step 1: Traverse tree and identify all leaf nodes with target value
Step 2: Delete found target leaves
Step 3: Repeat until no target leaves remain

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Remove all target leaves

Second Pass

New leaves exposed, remove target ones

Final Tree

No more target leaves remain

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool hasTargetLeaves(struct TreeNode* node, int target) {
    if (!node) return false;
    if (!node->left && !node->right) return node->val == target;
    return hasTargetLeaves(node->left, target) || hasTargetLeaves(node->right, target);
}

struct TreeNode* removeTargetLeaves(struct TreeNode* node, int target) {
    if (!node) return NULL;
    node->left = removeTargetLeaves(node->left, target);
    node->right = removeTargetLeaves(node->right, target);
    if (!node->left && !node->right && node->val == target) return NULL;
    return node;
}

int* solution(struct TreeNode* root, int target, int* returnSize) {
    while (hasTargetLeaves(root, target)) {
        root = removeTargetLeaves(root, target);
        if (!root) break;
    }
    
    *returnSize = 0;
    if (!root) return NULL;
    
    // Simplified: return single node value
    int* result = (int*)malloc(sizeof(int));
    result[0] = root->val;
    *returnSize = 1;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int target;
    scanf("%d", &target);
    
    int returnSize;
    int* result = solution(NULL, target, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, need O(n) passes, each taking O(n) time

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Multiple Pass Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler