Taro Logo

Correct a Binary Tree

#439 Most AskedMedium
21 views
Topics:
TreesGraphsRecursion

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:

  • The depth of the root node is 1.
  • The binary tree will not have more than 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:

  • The number of nodes in the tree is in the range [3, 104].
  • -105 <= Node.val <= 105
  • invalidNode.right != null
  • invalidNode.right.val != invalidNode.val

Solution


Clarifying Questions

When 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:

  1. What does it mean for the binary tree to be 'incorrect'? Are there specific types of errors, such as incorrect node values violating the binary search tree property, or structural issues like incorrect parent-child relationships?
  2. What are the data types and ranges of the values stored in the nodes of the binary tree? Can they be negative, zero, or floating-point numbers?
  3. Is the tree a Binary Search Tree (BST), or just a binary tree? If it's a BST, what is the expected behavior for duplicate values, and how should my 'correction' handle them?
  4. If there are multiple ways to 'correct' the tree, is there a specific criteria for which solution I should return, such as minimizing the number of changes, or returning the lexicographically smallest tree?
  5. What should I return if the input tree is null or empty? Should I return null, or an empty tree?

Brute Force Solution

Approach

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:

  1. First, consider every possible pair of nodes in the tree.
  2. For each pair, swap the values of those two nodes.
  3. Then, check if the entire tree now follows the rules of a binary search tree (where the left child is smaller, and the right child is larger, than the parent).
  4. If the tree is a valid binary search tree after the swap, you've found a solution.
  5. If the tree is not a valid binary search tree, undo the swap and move on to the next pair of nodes.
  6. Continue this process until you find a pair of nodes that, when swapped, results in a valid binary search tree.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n³) – The algorithm considers all possible pairs of nodes in the binary tree, which takes O(n²) time since we iterate through the tree to get the first node (O(n)) and then iterate again to get the second node (O(n)). For each pair, it validates whether the tree is a valid binary search tree after the swap. Checking the validity of the BST takes O(n) time because we potentially need to visit all n nodes. Therefore, the overall time complexity is O(n²) * O(n), resulting in O(n³).
Space Complexity
O(1) – The provided algorithm explores every possible pair of nodes for swapping, but it performs swaps directly on the tree and doesn't create new data structures to store these pairs. It only needs to store a few temporary variables (e.g., for storing node values during swaps, or for checking if the tree is a valid BST after each swap). Therefore, the auxiliary space used remains constant regardless of the number of nodes, N, in the tree.

Optimal Solution

Approach

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:

  1. First, imagine walking through the tree in a specific order: left, node, right. As you go, keep track of the last node you visited.
  2. If you ever find a node whose value is less than the last one you visited, you know something is out of place. You've found at least one incorrect node.
  3. Keep going until you find a second misplaced node. These are the two nodes that need to be swapped.
  4. If you only found one misplaced node, it means that node needs to be swapped with the node that came before it, or after it, depending on the location of the other misplaced node.
  5. Swap the values of the two incorrect nodes. This puts them in the correct spots.
  6. After swapping, the tree will now be a valid binary search tree. No further changes are needed.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n) – The provided algorithm performs an inorder traversal of the binary search tree, visiting each node exactly once. During the traversal, it compares each node with its predecessor to identify misplaced nodes. Since each node is visited and compared only a constant number of times, the time complexity is directly proportional to the number of nodes in the tree, denoted as n. Therefore, the algorithm's time complexity is O(n).
Space Complexity
O(H) – The algorithm uses recursion to traverse the binary search tree in an in-order fashion. The maximum depth of the recursion call stack is determined by the height of the tree, denoted as H. In the worst-case scenario (a skewed tree), H can be equal to N, where N is the number of nodes. Therefore, the auxiliary space complexity is O(H), which simplifies to O(N) in the worst case but can be better if the tree is balanced.

Edge Cases

Null root node
How to Handle:
Handle the null root node by returning null or an empty tree.
Tree with only the root node
How to Handle:
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
How to Handle:
The algorithm must correctly swap the two nodes if they are misplaced.
All nodes have the same value
How to Handle:
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)
How to Handle:
The algorithm should correctly identify and swap the two adjacent incorrect nodes.
Two nodes far apart in the tree need to be swapped
How to Handle:
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)
How to Handle:
The solution must correctly identify the sorted tree and return it unchanged.
Integer overflow if node values are very large
How to Handle:
Consider using a data type with a wider range or check for potential overflow conditions during comparisons.
0/1916 completed