Watch 6 video solutions for Correct a Binary Tree, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by Programming Live with Larry has 243 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have a binary tree with a small defect. There is exactly one invalid node where its right child incorrectly points to another node at the same depth but to the invalid node's right.
Given the root of the binary tree with this defect, root, return the root of the binary tree after removing this invalid node and every node underneath it (minus the node it incorrectly points to).
Custom testing:
The test input is read as 3 lines:
TreeNode rootint fromNode (not available to correctBinaryTree)int toNode (not available to correctBinaryTree)After the binary tree rooted at root is parsed, the TreeNode with value of fromNode will have its right child pointer pointing to the TreeNode with a value of toNode. Then, root is passed to correctBinaryTree.
Example 1:
Input: root = [1,2,3], fromNode = 2, toNode = 3 Output: [1,null,3] Explanation: The node with value 2 is invalid, so remove it.
Example 2:
Input: root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4 Output: [8,3,1,null,null,9,4,null,null,5,6] Explanation: The node with value 7 is invalid, so remove it and the node underneath it, node 2.
Constraints:
[3, 104].-109 <= Node.val <= 109Node.val are unique.fromNode != toNodefromNode and toNode will exist in the tree and will be on the same depth.toNode is to the right of fromNode.fromNode.right is null in the initial tree from the test data.Problem Overview: A binary tree contains one invalid node whose right pointer incorrectly points to another node on the same depth but to its right. Your task is to detect that corrupted node and remove the entire subtree rooted at it, returning the corrected tree.
Approach 1: Breadth-First Search + Hash Set (O(n) time, O(n) space)
Traverse the tree level by level using Breadth-First Search. The key trick is processing each level from right to left. Maintain a hash set storing nodes that have already been seen on the current or deeper levels. When visiting a node, check whether node.right already exists in the set. If it does, this node is the corrupted one because its right pointer illegally points to a node that appears later in the same level traversal. Remove this node by returning null to its parent. Hash lookups take O(1), so the traversal remains linear.
Approach 2: Depth-First Search + Hash Set (O(n) time, O(n) space)
A Depth-First Search can detect the same condition if you traverse the tree in right-to-left order. Start recursion from the root, always exploring the right child before the left. Maintain a hash set of visited nodes. When a node's right pointer references a node that already exists in the set, you have found the invalid node. Return null so the parent disconnects it. Because DFS explores the right side first, nodes that appear "to the right" in the same level get recorded earlier, making the corruption detectable.
The DFS approach maps naturally to recursion and keeps the code short. Each node is visited once, and each hash lookup is constant time, giving O(n) total work with O(n) auxiliary memory.
Recommended for interviews: The right-first DFS with a hash set is typically preferred. It clearly demonstrates understanding of hash tables and binary tree traversal order. BFS is equally valid and sometimes easier to reason about level relationships, but interviewers often expect the DFS variant because it removes the subtree cleanly during recursion while still achieving O(n) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Hash Set (Right-to-Left Level Traversal) | O(n) | O(n) | When reasoning about nodes on the same level is easier using level-order traversal. |
| DFS with Hash Set (Right-First Traversal) | O(n) | O(n) | General case and most common interview solution; simple recursive implementation. |