Skip to main content
Talentd

Correct a Binary Tree - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableTreeDepth-First SearchBreadth-First Search6 min readAsked at: Google
Practice this problem

Problem Statement

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 root
  • int 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:

  • The number of nodes in the tree is in the range [3, 104].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • fromNode != toNode
  • fromNode 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.

Approach Overview

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.

Solution

We design a function dfs(root) to handle the subtree with root as the root. If root is null or root.right has been visited, root is an invalid node, so we return null. Otherwise, we recursively process root.right and root.left, and return root.

Finally, we return dfs(root).

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++JavaScript

Python

Java

C++

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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.

Video Solution

1660. Correct a Binary Tree - Week 4/5 Leetcode October Challenge • Programming Live with Larry • 249 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Correct a Binary Tree easy or hard?
Correct a Binary Tree is generally considered a medium difficulty problem. The tree traversal itself is straightforward, but identifying the right-to-left traversal order and using a hash set to detect the invalid pointer is the key insight.
Correct a Binary Tree Python/Java solution
Most implementations use DFS with a hash set. The recursion explores the right subtree before the left subtree, records visited nodes, and returns null when the invalid node is detected. The same logic translates directly across Python, Java, C++, and JavaScript.
How to solve Correct a Binary Tree in O(n)?
Traverse the tree either with BFS (right-to-left per level) or DFS (right-first order) while storing visited nodes in a hash set. If a node's right child points to a node already in the set, that node is the corrupted one. Remove it by returning null from the parent link. Each node is processed once, resulting in O(n) time.
What is the best approach for Correct a Binary Tree?
The most common approach uses Depth-First Search with a hash set while traversing the tree from right to left. If a node's right pointer references a node already seen during traversal, that node is invalid and its subtree should be removed. This solution runs in O(n) time with O(n) extra space.
Is Correct a Binary Tree asked at Google/Amazon/Meta?
Binary tree correction and pointer validation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that combine tree traversal with hash sets or level-order reasoning are common in medium-level interview rounds.
What data structure is used in Correct a Binary Tree?
The solution relies on a hash set to track previously visited nodes and detect illegal right pointers. The traversal itself uses either Depth-First Search recursion or a Breadth-First Search queue over the binary tree.
What is the time complexity of Correct a Binary Tree?
Both DFS and BFS solutions visit each node once, giving O(n) time complexity where n is the number of nodes in the tree. A hash set is used to track visited nodes, which adds O(n) auxiliary space.

Ready to solve this problem?

Practice Correct a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Flatten a Multilevel Doubly Linked List

Next

Flatten Binary Tree to Linked List