We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Correct a Binary Tree

Number: 1796

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

A binary tree has a single irregularity: exactly one node (called the “defective” node) has its right pointer not pointing to a proper child but erroneously “stealing” a node already present at the same depth (to the right of it). Your task is to remove that defective node and its entire subtree (except for the node it mistakenly points to) and then return the fixed tree.

Key Insights

  • The defect appears “horizontally” in the tree: a node’s right pointer points to another node at the same level.
  • Because all Node.val’s are unique, comparing nodes by identity (or value) is safe.
  • A level order (BFS) traversal is ideal since the nodes that could be invalid are recognized by examining the nodes present on the same level.
  • When processing a level, if any node’s right child pointer points to a node that is present on that same level, it is the defective node.
  • Once the defective node is detected, remove it from its parent (by setting the corresponding pointer to null) and return the root immediately.

Space and Time Complexity

Time Complexity: O(n) – We traverse each node once. Space Complexity: O(n) – A queue (or level list) is used to store nodes from each level.

Solution

We solve the problem by performing a level order traversal using BFS while keeping not only the nodes of the current level but also remembering each node’s parent and whether it is a left or right child. For each level:

  1. Build a set (or hash set) of all nodes at that level.
  2. Iterate the nodes in left‑to‑right order. For each node, if its right pointer is not null and the node it points to belongs to the same level set, then that node is defective.
  3. Remove the defective node from its parent (if it is the left child then set parent.left to null; otherwise, set parent.right to null), and return the root immediately.
  4. If no defect is found on the current level, build the next level from the left and right children (making sure that if the same node appears twice, only the first encountered “legitimate” pointer is used). This approach only “sees” a node once per level. In a valid tree the children pointers would go to the next level; the horizontal edge (the defect) will make a child appear on the same level as the parent. When that happens, our check detects the duplicate and we perform the removal.

Code Solutions

# 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

def correctBinaryTree(root):
    # Start with a list representing the current level.
    # Each element is a tuple: (node, parent, isLeft) where parent is None for the root.
    level = [(root, None, None)]
    
    # Process level by level
    while level:
        # Build a set of node identities for the current level.
        current_set = set(node for node, _, _ in level)
        
        # Check each node in the current level for the defect.
        for node, parent, isLeft in level:
            # If the node's right pointer is not null and the node it points to
            # is among the nodes on the same level, then we have found the defect.
            if node.right is not None and node.right in current_set:
                # Remove the defective node from its parent.
                if parent:
                    if isLeft:
                        parent.left = None
                    else:
                        parent.right = None
                # Return the modified tree.
                return root
        
        # Build the next level. To avoid duplicates (in case the defect pointer
        # would otherwise add a node already seen as a legitimate child), we use a set.
        next_level = []
        next_set = set()
        for node, _, _ in level:
            if node.left:
                # Only add if not already added.
                if node.left not in next_set:
                    next_level.append((node.left, node, True))
                    next_set.add(node.left)
            if node.right:
                # Important: if node.right points to a node that would be added as a child,
                # it may be a duplicate because the defect gives an extra pointer.
                if node.right not in next_set:
                    next_level.append((node.right, node, False))
                    next_set.add(node.right)
        level = next_level

    return root
← Back to All Questions