Delete Leaves With a Given Value

Delete Leaves With a Given Value is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.

Problem statement

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.

Remove every leaf whose value equals target. Deletions are applied repeatedly: after deleting a leaf, its parent may become a leaf, and that parent must also be deleted if its value equals target. A leaf with any other value remains in the tree.

Return the root of the resulting tree. If the original tree is empty or the root is eventually deleted, return an empty tree, represented as []. The returned tree is serialized in level order using null for missing children.

Example 1:

Input: root = [5,3,8,3,4,null,3], target = 3 Output: [5,3,8,null,4] Explanation: The leftmost 3 and the right child of 8 are target-valued leaves, so they are removed. The other 3 still has child 4 and therefore is not a leaf, so it remains.

Example 2:

Input: root = [7,2,9,null,5,9,1], target = 9 Output: [7,2,9,null,5,null,1] Explanation: The 9 that is the left child of the right-side 9 is a leaf and is removed. The other 9 remains because it still has child 1.

Example 3:

Input: root = [], target = 6 Output: [] Explanation: The input tree is empty, so there are no leaves to remove.

Constraints:

- 0 <= number of nodes in root <= 3000 - 1 <= value of each node <= 1000 - 1 <= target <= 1000 - root describes a valid binary tree in level order - root is [] when the tree is empty - target is a JSON integer

Topics and companies

Topics: Binary Tree, Depth-First Search, Recursion, Tree.

How to practise Delete Leaves With a Given Value on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. 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.

Open Delete Leaves With a Given Value in the code editor, or read the Delete Leaves With a Given Value editorial for a worked solution with its approach and complexity analysis.

Where Delete Leaves With a Given Value sits in the DSA pattern sheet

Problems related to Delete Leaves With a Given Value

Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.