Post Number 400: BFS + DFS

This is my post number #400. I think I have this idea that when I retire I'm going to read all this shit... Illusion... 

In any case, here is the problem: Correct a Binary Tree - LeetCode

1660. Correct a Binary Tree

Medium

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.

Accepted

461

Submissions

571

I first tried an inverse-in-order approach, but that did not work. I was forced to look at some hints, and noticed when folks were suggesting a BFS followed by a DFS. Then it hit me:

a) Perform a BFS to find the bad node. Use a Hashtable and go with a straight BFS. You should be able to find it

b) Then perform a DFS with the result from (a). Keep track of the parent node, also keep track whether the offending node is the right child or left child. Then nullify it accordingly.

Code is down bellow, cheers, and Happy Thanksgiving!!!

public TreeNode CorrectBinaryTree(TreeNode root)
{
    RemoveBadNodeDFS(null, root, true, FindBadNodeBFS(root));
    return root;
}

public void RemoveBadNodeDFS(TreeNode parent,
                                TreeNode current,
                                bool isRightChild,
                                int badNode)
{
    if (current == null) return;
    if (current.val == badNode)
    {
        if (isRightChild) parent.right = null;
        else parent.left = null;
        return;
    }
    RemoveBadNodeDFS(current, current.right, true, badNode);
    RemoveBadNodeDFS(current, current.left, false, badNode);
}

private int FindBadNodeBFS(TreeNode root)
{
    if (root == null) return -1;

    Hashtable visited = new Hashtable();
    Queue queue = new Queue();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        TreeNode current = queue.Dequeue();

        if (current.right != null && visited.Contains(current.right.val)) return current.val;
        visited.Add(current.val, true);

        if (current.right != null) queue.Enqueue(current.right);
        if (current.left != null) queue.Enqueue(current.left);
    }

    return -1;
}