Correct A Binary Tree - Leetcode Solution

Problem Statement:

Given the root of a binary tree, then it may have a mistake in one of its node values.

You are given the root of a binary tree with exactly one value that needs to be changed to make the tree a valid binary tree.

Return the new root of the subtree with a value swapped.

Solution:

Approach:

The approach to solving the “Correct a Binary Tree” problem is simple:

1. First, we will find out the nodes that are conflicting i.e., nodes that are violating the rule of a binary tree.
2. We will perform in-order traversal of the binary tree and store the nodes in an array in increasing order.
3. We will then find the conflicting nodes and interchange their values.
4. Finally, we will return the root of the binary tree.

Algorithm:

1. Initialize an empty array to store in-order traversal of nodes.
2. Using a recursive in-order traversal method, traverse the tree and store the nodes in the array.
3. Find the two incorrect nodes, lowest and highest, by iterating over the array.
4. Swap the values of the lowest and highest incorrect nodes.
5. Return the root node of the modified binary tree.

Let's solve the “Correct a Binary Tree” problem step by step:

Step 1: We will initialize an array to store the in-order traversal nodes.

var inOrder = [];

Step 2: We will traverse the binary tree in-order storing the nodes in the array. We will use a recursive function called inorderTraversal() that takes two arguments: the root node of the binary tree and the inOrder array.

function inorderTraversal(node, inOrder) {
    if (node === null) {
        return;
    }
    inorderTraversal(node.left, inOrder);
    inOrder.push(node);
    inorderTraversal(node.right, inOrder);
}

This code recursively traverses the left sub-tree, stores the node in the array, and then traverses the right sub-tree.

Step 3: We will now find the nodes that need to be swapped. We will traverse the inOrder array and find the first and last node that violates the binary tree rule, i.e., the node that is greater than the next node. Let’s write a function called findIncorrectNodes() to find these nodes.

function findIncorrectNodes(root) {
    inOrder = [];
    inorderTraversal(root, inOrder);
    var lowest = null;
    var highest = null;
    for (var i = 0; i < inOrder.length - 1; i++) {
        if (inOrder[i].val > inOrder[i+1].val) {
            lowest = inOrder[i];
            break;
        }
    }
    for (var i = inOrder.length - 1; i >= 1; i--) {
        if (inOrder[i].val < inOrder[i-1].val) {
            highest = inOrder[i];
            break;
        }
    }
    return [lowest, highest];
}

Step 4: We will now swap the values of these two nodes. This is done by writing a function called swap() that takes the two nodes as input and swaps their values.

function swap(a, b) {
    var temp = a.val;
    a.val = b.val;
    b.val = temp;
}

Step 5: We will now call the above functions to solve the problem. We will call findIncorrectNodes() to get the nodes that need to be swapped, followed by swap() to swap the values of these nodes. Finally, we will return the root node of the binary tree.

var root = /*...*/;
var [lowest, highest] = findIncorrectNodes(root);
swap(lowest, highest);
return root;

Now we have a complete solution for the “Correct a Binary Tree” problem on LeetCode.

1