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 right of itself.
Given the root of the binary tree, find the invalid node and correct it by setting the right child to null.
Return the root of the binary tree after correcting it.
Note:
1.104 nodes.Example 1:
Input: root = [1,2,3] Output: [1,2,3] Explanation: The binary tree is perfect, so there is no defect.
Example 2:
Input: root = [1,2,3,null,4] Output: [1,2,3,null,4] Explanation: There is no defect in the binary tree.
Example 3:
Input: root = [1,2,3,null,4,null,5] Output: [1,2,3,null,4,null,5] Explanation: There is no defect in the binary tree.
Example 4:
Input: root = [1,2,3,null,4,5,6,null,null,7,8] Output: [1,2,3,null,4,null,6,null,null,7,8] Explanation: The node with value 5 is an invalid node because its right child incorrectly points to the node with value 6. We correct the binary tree by setting the right child of the node with value 5 to null.
Example 5:
Input: root = [1,2,3,null,4,5,6,null,null,null,null,7,8] Output: [1,2,3,null,4,5,6,null,null,null,null,7,8] Explanation: The node with value 4 is an invalid node because its right child incorrectly points to the node with value 5. We correct the binary tree by setting the right child of the node with value 4 to null.
Constraints:
[3, 104].-105 <= Node.val <= 105invalidNode.right != nullinvalidNode.right.val != invalidNode.valWhen you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
Imagine you have a binary tree where two nodes are swapped accidentally. The brute force method involves trying every possible pair of nodes in the tree and swapping them, one pair at a time. After each swap, we check if the tree is now a valid binary search tree.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def correct_binary_tree(root):
nodes = []
def inorder_traversal(node):
if node:
inorder_traversal(node.left)
nodes.append(node)
inorder_traversal(node.right)
inorder_traversal(root)
# We need to swap every single possible node combination
# to ensure all possible corrections are attempted
for first_node_index in range(len(nodes)):
for second_node_index in range(first_node_index + 1, len(nodes)):
first_node = nodes[first_node_index]
second_node = nodes[second_node_index]
# Swap the values of the two nodes
first_node.value, second_node.value = second_node.value, first_node.value
# We are checking to see if the current state of the tree is a valid BST
# because we want to find when the swap is a success
if is_valid_bst(root):
return root
# Swap the values back if the tree is not a valid BST
first_node.value, second_node.value = second_node.value, first_node.value
# If no swaps work, we return None
return None
def is_valid_bst(node, min_value=float('-inf'), max_value=float('inf')):
if not node:
return True
# Check current node against BST properties
if not (min_value < node.value < max_value):
return False
# Recursively check subtrees
return (is_valid_bst(node.left, min_value, node.value)
and is_valid_bst(node.right, node.value, max_value))
def create_tree(values):
if not values:
return None
root = TreeNode(values[0])
queue = [root]
index = 1
while queue and index < len(values):
node = queue.pop(0)
if values[index] is not None:
node.left = TreeNode(values[index])
queue.append(node.left)
index += 1
if index < len(values) and values[index] is not None:
node.right = TreeNode(values[index])
queue.append(node.right)
index += 1
return root
The tree should be a binary search tree, but it's not. The optimal approach involves finding the incorrectly placed nodes and then swapping them in a clever way to fix the tree's structure without brute-force searching.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def correct_binary_tree(root):
first_misplaced_node = None
second_misplaced_node = None
previous_node = None
def inorder_traversal(node):
nonlocal first_misplaced_node, second_misplaced_node, previous_node
if node is None:
return
inorder_traversal(node.left)
# Check for misplaced node
if previous_node and node.value < previous_node.value:
if not first_misplaced_node:
# This is the first out-of-order node
first_misplaced_node = previous_node
second_misplaced_node = node
else:
# Found the second out-of-order node
second_misplaced_node = node
previous_node = node
inorder_traversal(node.right)
inorder_traversal(root)
# Swap the values of the misplaced nodes
if first_misplaced_node and second_misplaced_node:
first_misplaced_node.value, second_misplaced_node.value = second_misplaced_node.value, first_misplaced_node.value
return root| Case | How to Handle |
|---|---|
| Null root node | Handle the null root node by returning null or an empty tree. |
| Tree with only the root node | The solution should correctly identify if the root node is the only node out of place. |
| Tree with two nodes where the root needs to be swapped with the only child | The algorithm must correctly swap the two nodes if they are misplaced. |
| All nodes have the same value | The algorithm must identify if no corrections are needed, since no swap can make it more correct. |
| Two adjacent nodes need to be swapped (e.g., in-order traversal yields only two out-of-order nodes) | The algorithm should correctly identify and swap the two adjacent incorrect nodes. |
| Two nodes far apart in the tree need to be swapped | Ensure that the algorithm can handle cases where incorrect nodes are not close to each other. |
| The tree is already correct (no nodes need to be swapped) | The solution must correctly identify the sorted tree and return it unchanged. |
| Integer overflow if node values are very large | Consider using a data type with a wider range or check for potential overflow conditions during comparisons. |