LeetCode 1660 - Correct a Binary Tree

Here is a complete, detailed technical solution guide for LeetCode 1660 - Correct a Binary Tree, formatted exactly as re

leetcodemediumhash-tabletreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 1660

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Here is a complete, detailed technical solution guide for LeetCode 1660 - Correct a Binary Tree, formatted exactly as requested.

Problem Understanding

The problem presents a binary tree that has a subtle defect: there is exactly one invalid node, whose right child incorrectly points to another node on the same depth but to the right of itself. Our task is to remove the invalid node and its subtree, while preserving the rest of the tree.

The input is the root of the binary tree. In the test setup, the node fromNode has its right pointer incorrectly pointing to toNode on the same depth. Our function does not receive fromNode or toNode directly; it must infer the invalid node by tree traversal.

The constraints are important:

  • All node values are unique, which allows us to track nodes using a hash map of seen values.
  • The tree can be large, up to 10,000 nodes, so an inefficient solution that examines all pairs of nodes repeatedly will be too slow.
  • The problem guarantees exactly one invalid node; we do not need to handle multiple errors.
  • fromNode.right is null in the original tree, so the invalid right pointer is the only structural anomaly.

Edge cases to note include trees where the invalid node is the root, invalid nodes at the last level, or trees with only left children besides the defect. These could trip up naive traversal if we do not track seen nodes carefully.

Approaches

Brute-Force Approach: We could traverse each node and, for each node, scan all nodes at the same depth to see if its right pointer points to another node. Once we find a node pointing right to another node at the same depth, we remove it and its subtree. This works because it directly checks the invalid pointer but is inefficient: for each node, scanning the same level takes O(n) time. In the worst case, this becomes O(n²) time, which is unacceptable for n = 10⁴.

Optimal Approach: The key observation is that a BFS level-order traversal naturally exposes nodes at the same depth. If we traverse the tree level by level, we can maintain a set of nodes already seen in this level. For each node, if its right child points to a node already in this set, it is the invalid node. We can then remove it by setting the corresponding parent pointer to null. This approach guarantees O(n) time because each node is visited exactly once, and checking membership in a set is O(1).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Check all nodes at same depth for each node
Optimal (BFS with hash set) O(n) O(n) BFS guarantees level-order and allows detection with hash set

Algorithm Walkthrough

  1. Initialize a queue with the root node for BFS traversal.

  2. While the queue is not empty, process nodes level by level:

  3. Create a set called seen to record all nodes at the current level.

  4. For each node in the current level:

  5. If the node has a right child and node.right is in seen, this is the invalid node.

  6. Remove the invalid node by setting its parent pointer to null.

  7. Otherwise, add the node to seen.

  8. Add children of the current node to the queue for processing the next level.

  9. Continue until the BFS traversal finishes.

  10. Return the root node, which now points to the corrected tree.

Why it works: BFS processes nodes level by level, so any node pointing right to a node already seen at the same level must be the invalid node. The invariant is that seen contains all nodes to the left at the current depth, so checking the right pointer against seen reliably detects the defect. Removing the node immediately ensures no traversal of its children, which aligns with the problem requirement.

Python Solution

# 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
from collections import deque

class Solution:
    def correctBinaryTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        queue = deque([root])
        parent_map = {root: None}  # Keep track of parents to remove invalid node
        
        while queue:
            level_size = len(queue)
            seen = set()
            for _ in range(level_size):
                node = queue.popleft()
                
                # Check if the right child points to a node already seen
                if node.right and node.right in seen:
                    parent = parent_map[node]
                    if parent:
                        if parent.left == node:
                            parent.left = None
                        else:
                            parent.right = None
                    else:
                        root = None  # Edge case: root itself is invalid
                    return root  # Only one invalid node exists
                
                seen.add(node)
                
                if node.left:
                    queue.append(node.left)
                    parent_map[node.left] = node
                if node.right:
                    queue.append(node.right)
                    parent_map[node.right] = node
                    
        return root

Explanation: We perform a BFS using a queue. seen tracks nodes at the current level. parent_map allows us to remove the invalid node by updating the parent’s pointer. As soon as the invalid node is detected, we remove it and return the corrected tree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func correctBinaryTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    type pair struct {
        node   *TreeNode
        parent *TreeNode
    }

    queue := []pair{{root, nil}}

    for len(queue) > 0 {
        levelSize := len(queue)
        seen := make(map[*TreeNode]bool)

        for i := 0; i < levelSize; i++ {
            p := queue[0]
            queue = queue[1:]
            node := p.node
            parent := p.parent

            if node.Right != nil && seen[node.Right] {
                if parent != nil {
                    if parent.Left == node {
                        parent.Left = nil
                    } else {
                        parent.Right = nil
                    }
                } else {
                    root = nil
                }
                return root
            }

            seen[node] = true

            if node.Left != nil {
                queue = append(queue, pair{node.Left, node})
            }
            if node.Right != nil {
                queue = append(queue, pair{node.Right, node})
            }
        }
    }
    return root
}

Explanation: The Go implementation mirrors Python. We use a pair struct to track both the node and its parent. A map seen detects the invalid right pointer. Removing the node is straightforward by checking if it is a left or right child of its parent.

Worked Examples

Example 1: root = [1,2,3], fromNode = 2, toNode = 3

Level-order traversal:

Level Nodes Seen set Action
0 1 {} Add 1 to seen, enqueue children [2,3]
1 2 {} Add 2 to seen, enqueue left/right (none/3)
1 3 {2} Right pointer is fine, add 3 to seen

Detect invalid: Node 2 right points to 3 which is in seen → remove node 2

Output: [1,null,3]

Example 2: root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4

Level-order traversal and seen sets detect that 7’s right points to 4 already seen → remove node 7 and its subtree 2

Output: [8,3,1,null,null,9,4,null,null,5,6]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited once in BFS
Space O(n) Queue can hold up to all nodes at the last level, parent map stores O(n) nodes

The optimal BFS approach is linear in both time and space, suitable for the problem constraints.

Test Cases

# Provided examples
assert Solution().correctBinaryTree(TreeNode(1, TreeNode(2), TreeNode(3))).val == 1  # Example 1
root2 = TreeNode(8,
                 TreeNode(3, TreeNode(7), TreeNode(1)),
                 TreeNode(9, TreeNode(5), TreeNode(6)))
assert Solution().correctBinaryTree(root2).val == 8  # Example 2

# Edge case: root itself invalid
root3 = TreeNode(1, TreeNode(2), TreeNode(3))
root3.right.right = root3.left
assert Solution().correctBinaryTree(root3).val == 3

# Large tree with single invalid node
root4 = Tree