Delete Leaves With a Given Value
Medium · Graphs · Explanation and code example
Iterative Postorder Traversal (Optimal)
How it works
We can optimize the iterative approach by using a standard postorder traversal pattern without maintaining a separate parent map. The stack itself naturally tracks the parent: after processing a node, the next item on the stack is its parent. We use a visited pointer to avoid reprocessing the right subtree.
Steps
- Initialize a stack and a
visitedpointer to track the last processed node. - Use two nested loops: the outer continues while the stack or current pointer is not empty.
- Inner loop: traverse left as far as possible, pushing nodes onto the stack.
- Peek the top node. If it has an unvisited right child, move to the right.
- Otherwise, pop the node. If it is a leaf with the target value, delete it by updating the parent's reference (the new top of the stack).
- If not deleted, mark it as
visited. - Return the root.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Using Preorder Instead of Postorder
Deleting leaves must be done bottom-up. If you check a node before processing its children (preorder), you miss newly created leaves when children are deleted.
Not Checking Both Conditions for Leaf Deletion
A node should only be deleted if it is both a leaf (no children) AND has the target value. Missing either condition causes incorrect deletions.
Python code example
from typing import Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
if not root:
return None
stack = []
cur = root
visited = None
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack[-1]
if cur.right and cur.right != visited:
cur = cur.right
continue
stack.pop()
if not cur.left and not cur.right and cur.val == target:
if not stack:
return None
parent = stack[-1]
if parent.left == cur:
parent.left = None
elif parent.right == cur:
parent.right = None
else:
visited = cur
cur = None
return root
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* removeLeafNodes(TreeNode* root, int target) {
if (!root) return nullptr;
stack<TreeNode*> stack;
TreeNode* cur = root;
TreeNode* visited = nullptr;
while (!stack.empty() || cur) {
while (cur) {
stack.push(cur);
cur = cur->left;
}
cur = stack.top();
if (cur->right && cur->right != visited) {
cur = cur->right;
continue;
}
stack.pop();
if (!cur->left && !cur->right && cur->val == target) {
if (stack.empty()) return nullptr;
TreeNode* parent = stack.top();
if (parent->left == cur) {
parent->left = nullptr;
} else if (parent->right == cur) {
parent->right = nullptr;
}
} else {
visited = cur;
}
cur = nullptr;
}
return root;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.