Delete Leaves With a Given Value

Delete Leaves With a Given Value: the approach in brief

The problem

You are given the root of a binary tree in root and an integer target. A binary tree consists of nodes, each with a value and up to two children; a missing child is represented by null in the level-order input. A leaf is a node that has neither a left child nor a right child.

Pattern

Delete Leaves With a Given Value is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Postorder Traversal subpattern. The pattern covers preorder, inorder, level order traversal, LCA, and serialization

Approach outline

1. A node can be classified correctly only after its children have been processed.
2. Let each recursive call return the subtree that should replace the current node.
3. Once both returned child references are known, check whether the current node has become a leaf and whether its value equals `target`.

Complexity

The reference solution runs in O(n), where n is the number of nodes in the tree. time and O(h) auxiliary space for recursion, where h is the tree height. space.