CareerCup

Since it's not a regular binary tree, but a binary search tree, and taking in account that parent 1 and 2 are not ancestors (meaning that the parents are located in two different subtrees), having 2 parents breaks the property of a binary search tree. So, we can just check if the child's value satisfies the property or not.
In the code below, I assume that in the BST, left child's value must be less, and the right child's value must be greater or equal to the value of the parent.

#include <iostream>

using namespace std;

class Node {
	public:
		Node(int val)
		{
			val_ = val;
			left_ = right_ = NULL;
		}
		int val_;
		Node *left_, *right_;
};

void FixBst(Node *n, int upper = numeric_limits<int>::max(), int lower = numeric_limits<int>::min(), Node *parent = NULL)
{
	if (n) {
		if (parent) {
			if (n->val_ < lower ||
				n->val_ >= upper)
			{
				cout << parent->val_ << "->" << n->val_ << "\n";
				if (parent->left_ == n) {
					parent->left_ = NULL;
				} else {
					parent->right_ = NULL;
				}
			}
		}
		FixBst(n->left_, min(upper, n->val_), lower, n);
		FixBst(n->right_, upper, max(lower, n->val_), n);
	}
}

int main()
{
/*
      (7)
      / \
    (5) (9)
      \ /
      (6)
*/
	Node n1(7), n2(5), n3(9), n4(6);
	n1.left_ = &n2;
	n1.right_ = &n3;
	n2.right_ = &n4;
	n3.left_ = &n4;

	FixBst(&n1);
	return 0;
}

We use BFS to traverse the tree while keeping track on each child's parent
The same can be coded using recursion. As the question stated: this method fixes only one broken node (it can be adjusted to continue and scan for more double links):

#include "CommonHeader.h"

class BSTNode
{
public:
    std::string label;
    std::vector<BSTNode*> children;
    BSTNode(const std::string& n)
        : label(n)
    {
    }
    BSTNode() {}
};

static std::unordered_map<std::string, BSTNode> G;
// Our test tree
//                           (a)
//                           / \ 
//                          /   \ 
//                         (b) (c)
//                         |   /
//                         |  /
//                         (d)
BSTNode* makeTestTree()
{
    G["a"] = BSTNode("a");
    G["b"] = BSTNode("b");
    G["c"] = BSTNode("c");
    G["d"] = BSTNode("d");

    G["a"].children.push_back(&G["b"]);
    G["a"].children.push_back(&G["c"]);
    G["c"].children.push_back(&G["d"]); // double parent
    G["b"].children.push_back(&G["d"]); // double parent
    return &G["a"];
}

void fixDoubleParentNode()
{
    BSTNode* bst = makeTestTree();
    
    // Keep track of the parents
    std::unordered_map<BSTNode*, BSTNode*> Parents;
    
    // Use BFS with Queue (we can apply the same logic with recursion)
    std::queue<BSTNode*> q;
    q.push(bst);
    Parents[bst] = nullptr;
    while(!q.empty()) {
        BSTNode* node = q.front();
        q.pop();

        for(size_t i = 0; i < node->children.size(); ++i) {
            BSTNode* child = node->children[i];
            if(Parents.count(child)) {
                // already visited this child
                node->children.erase(node->children.begin() + i);
                std::cout << "Found duplicate parenting for node: " << child->label
                          << " faulty parent: " << node->label << " is removed" << std::endl;
                return;
            } else {
                Parents[child] = node;
                q.push(child);
            }
        }
    }
}

public class FixBst
{
	public static void main(String args[])
	{
		TreeNode root= new TreeNode(3);
		root.left = new TreeNode(1);
		root.right = new TreeNode(6);
		root.left.right = new TreeNode(2);
		root.right.left = root.left.right;

		FixBst f = new FixBst();
		f.print(root);
		f.fix(root, Integer.MIN_VALUE, Integer.MAX_VALUE, null);
		System.out.println();
		f.print(root);

	}

	public void fix(TreeNode root, int min, int max, TreeNode parent)
	{
		if(root==null)
			return;
		if(root.val > min && root.val <= max)
		{
			fix(root.left, min, root.val, root);
			fix(root.right, root.val, max, root);
		}
		else
		{
			if(parent.left.val == root.val)
				parent.left = null;
			else if(parent.right.val == root.val)
				parent.right = null;
		}
	} 

	private void print(TreeNode root)
	{
		if(root==null)
			return;

		print(root.left);
		System.out.print(root.val+"\t");
		print(root.right);
	}
}

class TreeNode
{
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int val)
	{
		this.val = val;
	}
}