Correct a Binary Tree

medium tree bfs dfs hash set

Problem

A binary tree has exactly one defect: a single node's right pointer was redirected to a different node that appears later in level order (same level to its right, or a deeper level). Find that defective node and remove it (along with its subtree) so the tree becomes valid again. Return the root.

Because the bad pointer always points forward in a level-order scan, if we walk each level right to left we will see the target of the bad pointer before we see the node that owns it.

Inputroot = [1,2,3], with node 2's right wrongly pointing to node 3

Output[1,null,3]

Node 2's right points forward to 3 (already seen). Node 2 is defective, so it is removed, leaving 1 with only the right child 3.

level-order (use "null" for missing children)

defective node value (its right is redirected)

from collections import deque

def correct_binary_tree(root):
    seen = set()
    queue = deque([root])
    while queue:
        node = queue.popleft()
        seen.add(node)
        if node.right and node.right in seen:
            if node.parent.right is node:
                node.parent.right = None
            else:
                node.parent.left = None
            return root
        if node.right:
            node.right.parent = node
            queue.append(node.right)
        if node.left:
            node.left.parent = node
            queue.append(node.left)
    return root

function correctBinaryTree(root) {
  const seen = new Set();
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    seen.add(node);
    if (node.right && seen.has(node.right)) {
      node.parent.right === node
        ? (node.parent.right = null)
        : (node.parent.left = null);
      return root;
    }
    if (node.right) { node.right.parent = node; queue.push(node.right); }
    if (node.left) { node.left.parent = node; queue.push(node.left); }
  }
  return root;
}

class Solution {
    public TreeNode correctBinaryTree(TreeNode root) {
        Set<TreeNode> seen = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            seen.add(node);
            if (node.right != null && seen.contains(node.right)) {
                if (node.parent.right == node) node.parent.right = null;
                else node.parent.left = null;
                return root;
            }
            if (node.right != null) { node.right.parent = node; queue.offer(node.right); }
            if (node.left != null) { node.left.parent = node; queue.offer(node.left); }
        }
        return root;
    }
}

TreeNode* correctBinaryTree(TreeNode* root) {
    unordered_set<TreeNode*> seen;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        seen.insert(node);
        if (node->right && seen.count(node->right)) {
            if (node->parent->right == node) node->parent->right = nullptr;
            else node->parent->left = nullptr;
            return root;
        }
        if (node->right) { node->right->parent = node; q.push(node->right); }
        if (node->left) { node->left->parent = node; q.push(node->left); }
    }
    return root;
}

Explanation

The guarantee that the bad right pointer always points to a node that comes later in level order is the whole key. If we do a normal BFS but enqueue each node's right child before its left child, we process every level from right to left.

We keep a hash set of nodes we have already dequeued. The moment we dequeue a node whose right child is already in that set, we have found the defect: the right pointer jumped forward to a node we visited earlier in the same right-to-left sweep.

That current node is the one to delete. We reach its parent (tracked while enqueuing) and null out whichever child pointer led to it, detaching the bad node and its subtree.

Only one defect exists, so we can return immediately after fixing it. Everything before that point was a normal, correctly linked node.

Example: if node 2's right was redirected to 3, the right-to-left BFS sees 3 first, adds it to seen, then dequeues 2 and notices 2.right == 3 is already seen → remove node 2, leaving the tree valid.

Time: O(n) Space: O(n)