Remove edges connected to a node such that the three given nodes are in different trees

0 0 9 minutes read

Given a binary tree and 3 nodes a, b and c, the task is to find a node in the tree such that after removing all the edge connected to that node, a, b and c are in three different trees. Given below is a tree with input nodes as c, j and o.

In the above tree, if node i gets disconnected from the tree, then the given nodes c, j, and o will be in three different trees which have been shown below.

Tree with edges removed from the selected node

A simple approach is to find LCA of all possible pairs of nodes given. Let,

lca of ( a, b) = x
lca of (b, c) = y
lca of (c, a) = z

In any case, either of (x, y), (y, z), (z, x) or (x, y, z) will always be the same. In the first three cases, return the node which is not the same. In the last case returning any node of x, y or z will give the answer. Below is the implementation of the above approach:

C++

// C++ program for disconnecting a
// node to result in three different tree
#include <bits/stdc++.h>
using namespace std;
 
// node class
struct Node {
    int key;
    struct Node *left, *right;
};
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
// LCA function taken from the above link mentioned
// This function returns a pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and n2
// are present in Binary Tree
struct Node* findLCA(struct Node* root, int n1, int n2)
{
    // Base case
    if (root == NULL)
        return NULL;
 
    // If either n1 or n2 matches with root's key, report
    // the presence by returning root (Note that if a key is
    // ancestor of other, then the ancestor key becomes LCA
    if (root->key == n1 || root->key == n2)
        return root;
 
    // Look for keys in left and right subtrees
    Node* left_lca = findLCA(root->left, n1, n2);
    Node* right_lca = findLCA(root->right, n1, n2);
 
    // If both of the above calls return Non-NULL, then one key
    // is present in once subtree and other is present in other,
    // So this node is the LCA
    if (left_lca && right_lca)
        return root;
 
    // Otherwise check if left subtree or right subtree is LCA
    return (left_lca != NULL) ? left_lca : right_lca;
}
 
// the function assumes a, b, c are present in the tree
// and returns a node disconnecting which
// results in all three nodes in different trees
Node* findNode(Node* root, int a, int b, int c)
{
    // lca of a, b
    Node* x = findLCA(root, a, b);
 
    // lca of b, c
    Node* y = findLCA(root, b, c);
 
    // lca of c, a
    Node* z = findLCA(root, c, a);
 
    if (x->key == y->key)
        return z;
    else if (x->key == z->key)
        return y;
    else
        return x;
}
 
// Driver Code
int main()
{
    // Declare tree
    // Insert elements in the tree
    Node* root = newNode(1);
 
    root->left = newNode(2);
    root->right = newNode(3);
 
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
 
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(11);
 
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->left = newNode(12);
    root->right->left->right = newNode(13);
    root->right->right->left = newNode(14);
    root->right->right->right = newNode(15);
 
    /*
            1
        /     \
       2       3
     /  \     /  \
    4   5     6    7
   /\  / \   / \  / \
  8 9 10 11 12 13 14 15     
                           */
 
    // update all the suitable_children
    // keys of all the nodes in O( N )
 
    cout << "Disconnect node "
         << findNode(root, 5, 6, 15)->key
         << " from the tree";
 
    return 0;
}

Java

// Java program for disconnecting a 
// node to result in three different tree 
public class RemoveEdge {
 
    // LCA function taken from the above link mentioned 
    // This function returns a pointer to LCA of two given 
    // values n1 and n2. This function assumes that n1 and n2 
    // are present in Binary Tree 
    static Node findLCA(Node root, int n1, int n2) 
    { 
        // Base case 
        if (root == null) 
            return root; 
   
        // If either n1 or n2 matches with root's key, report 
        // the presence by returning root (Note that if a key is 
        // ancestor of other, then the ancestor key becomes LCA 
        if (root.key == n1 || root.key == n2) 
            return root; 
   
        // Look for keys in left and right subtrees 
        Node left_lca = findLCA(root.left, n1, n2); 
        Node right_lca = findLCA(root.right, n1, n2); 
   
        // If both of the above calls return Non-NULL, then one key 
        // is present in once subtree and other is present in other, 
        // So this node is the LCA 
        if (left_lca!=null && right_lca!=null) 
            return root; 
   
        // Otherwise check if left subtree or right subtree is LCA 
        return (left_lca != null) ? left_lca : right_lca; 
    } 
   
    // the function assumes a, b, c are present in the tree 
    // and returns a node disconnecting which 
    // results in all three nodes in different trees 
    static Node findNode(Node root, int a, int b, int c) 
    { 
        // lca of a, b 
        Node x = findLCA(root, a, b); 
        // lca of b, c 
        Node y = findLCA(root, b, c); 
        // lca of c, a 
        Node z = findLCA(root, c, a); 
   
        if (x.key == y.key) 
            return z; 
        else if (x.key == z.key) 
            return y; 
        else
            return x; 
    } 
 
    public static void main(String args[]) {
        Node root = new Node(1); 
        root.left = new Node(2); 
        root.right = new Node(3); 
        root.left.left = new Node(4); 
        root.left.right = new Node(5); 
        root.left.left.left = new Node(8); 
        root.left.left.right = new Node(9); 
        root.left.right.left = new Node(10); 
        root.left.right.right = new Node(11); 
        root.right.left = new Node(6); 
        root.right.right = new Node(7); 
        root.right.left.left = new Node(12); 
        root.right.left.right = new Node(13); 
        root.right.right.left = new Node(14); 
        root.right.right.right = new Node(15); 
        System.out.print("Disconnect node "+findNode(root, 5, 6, 15).key+" from the tree");
    }
}
 
// Node class 
class Node { 
    int key; 
    Node left, right; 
    Node (int data)
    {
        this.key=data;
    }
}; 
//This code is contributed by Gaurav Tiwari

Python3

# Python 3 program for disconnecting a
# node to result in three different tree
class RemoveEdge :
   
    # LCA function taken from the above link mentioned
    # This function returns a pointer to LCA of two given
    # values n1 and n2. This function assumes that n1 and n2
    # are present in Binary Tree
    @staticmethod
    def  findLCA( root,  n1,  n2) :
       
        # Base case
        if (root == None) :
            return root
           
        # If either n1 or n2 matches with root's key, report
        # the presence by returning root (Note that if a key is
        # ancestor of other, then the ancestor key becomes LCA
        if (root.key == n1 or root.key == n2) :
            return root
           
        # Look for keys in left and right subtrees
        left_lca = RemoveEdge.findLCA(root.left, n1, n2)
        right_lca = RemoveEdge.findLCA(root.right, n1, n2)
         
        # If both of the above calls return Non-NULL, then one key
        # is present in once subtree and other is present in other,
        # So this node is the LCA
        if (left_lca != None and right_lca != None) :
            return root
           
        # Otherwise check if left subtree or right subtree is LCA
        return left_lca if (left_lca != None) else right_lca
       
    # the function assumes a, b, c are present in the tree
    # and returns a node disconnecting which
    # results in all three nodes in different trees
    @staticmethod
    def  findNode( root,  a,  b,  c) :
       
        # lca of a, b
        x = RemoveEdge.findLCA(root, a, b)
         
        # lca of b, c
        y = RemoveEdge.findLCA(root, b, c)
         
        # lca of c, a
        z = RemoveEdge.findLCA(root, c, a)
        if (x.key == y.key) :
            return z
        elif(x.key == z.key) :
            return y
        else :
            return x
    @staticmethod
    def main( args) :
        root = Node(1)
        root.left = Node(2)
        root.right = Node(3)
        root.left.left = Node(4)
        root.left.right = Node(5)
        root.left.left.left = Node(8)
        root.left.left.right = Node(9)
        root.left.right.left = Node(10)
        root.left.right.right = Node(11)
        root.right.left = Node(6)
        root.right.right = Node(7)
        root.right.left.left = Node(12)
        root.right.left.right = Node(13)
        root.right.right.left = Node(14)
        root.right.right.right = Node(15)
        print("Disconnect node " + str(RemoveEdge.findNode(root, 5, 6, 15).key) + " from the tree", end ="")
# Node class
class Node :
    key = 0
    left = None
    right = None
    def __init__(self, data) :
        self.key = data
     
if __name__=="__main__":
    RemoveEdge.main([])
     
    # This code is contributed by aadityaburujwale.

C#

// C# program for disconnecting a 
// node to result in three different tree 
using System;
 
public class RemoveEdge
{ 
 
    // LCA function taken from the 
    // above link mentioned This function
    // returns a pointer to LCA of two given 
    // values n1 and n2. This function
    // assumes that n1 and n2 
    // are present in Binary Tree 
    static Node findLCA(Node root, int n1, int n2) 
    { 
        // Base case 
        if (root == null) 
            return root; 
     
        // If either n1 or n2 matches 
        // with root's key, report 
        // the presence by returning 
        // root (Note that if a key is 
        // ancestor of other, then the 
        // ancestor key becomes LCA 
        if (root.key == n1 || root.key == n2) 
            return root; 
     
        // Look for keys in left and right subtrees 
        Node left_lca = findLCA(root.left, n1, n2); 
        Node right_lca = findLCA(root.right, n1, n2); 
     
        // If both of the above calls 
        // return Non-NULL, then one key 
        // is present in once subtree and 
        // other is present in other, 
        // So this node is the LCA 
        if (left_lca!=null && right_lca!=null) 
            return root; 
     
        // Otherwise check if left 
        // subtree or right subtree is LCA 
        return (left_lca != null) ? left_lca : right_lca; 
    } 
     
    // the function assumes a, b, c 
    // are present in the tree and returns
    // a node disconnecting which results
    // in all three nodes in different trees 
    static Node findNode(Node root, int a, int b, int c) 
    { 
        // lca of a, b 
        Node x = findLCA(root, a, b); 
         
        // lca of b, c 
        Node y = findLCA(root, b, c); 
         
        // lca of c, a 
        Node z = findLCA(root, c, a); 
     
        if (x.key == y.key) 
            return z; 
        else if (x.key == z.key) 
            return y; 
        else
            return x; 
    } 
 
    // Driver code
    public static void Main(String []args) 
    { 
        Node root = new Node(1); 
        root.left = new Node(2); 
        root.right = new Node(3); 
        root.left.left = new Node(4); 
        root.left.right = new Node(5); 
        root.left.left.left = new Node(8); 
        root.left.left.right = new Node(9); 
        root.left.right.left = new Node(10); 
        root.left.right.right = new Node(11); 
        root.right.left = new Node(6); 
        root.right.right = new Node(7); 
        root.right.left.left = new Node(12); 
        root.right.left.right = new Node(13); 
        root.right.right.left = new Node(14); 
        root.right.right.right = new Node(15); 
        Console.Write("Disconnect node "+
                        findNode(root, 5, 6, 15).key+
                        " from the tree"); 
    } 
} 
 
// Node class 
public class Node 
{ 
    public int key; 
    public Node left, right; 
    public Node (int data) 
    { 
        this.key=data; 
    } 
}; 
 
// This code contributed by Rajput-Ji

Javascript

// node class
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
 
function newNode(key) {
  let temp = new Node(key);
  return temp;
}
 
// LCA function
function findLCA(root, n1, n2) {
  // Base case
  if (root == null) {
    return null;
  }
 
  // If either n1 or n2 matches with root's key, report
  // the presence by returning root (Note that if a key is
  // ancestor of other, then the ancestor key becomes LCA
  if (root.key == n1 || root.key == n2) {
    return root;
  }
 
  // Look for keys in left and right subtrees
  let left_lca = findLCA(root.left, n1, n2);
  let right_lca = findLCA(root.right, n1, n2);
 
  // If both of the above calls return Non-NULL, then one key
  // is present in once subtree and other is present in other,
  // So this node is the LCA
  if (left_lca && right_lca) {
    return root;
  }
 
  // Otherwise check if left subtree or right subtree is LCA
  return left_lca != null ? left_lca : right_lca;
}
 
// the function assumes a, b, c are present in the tree
// and returns a node disconnecting which
// results in all three nodes in different trees
function findNode(root, a, b, c) {
  // lca of a, b
  let x = findLCA(root, a, b);
 
  // lca of b, c
  let y = findLCA(root, b, c);
 
  // lca of c, a
  let z = findLCA(root, c, a);
 
  if (x.key == y.key) {
    return z;
  } else if (x.key == z.key) {
    return y;
  } else {
    return x;
  }
}
 
// Declare tree
// Insert elements in the tree
let root = newNode(1);
 
root.left = newNode(2);
root.right = newNode(3);
 
root.left.left = newNode(4);
root.left.right = newNode(5);
 
root.left.left.left = newNode(8);
root.left.left.right = newNode(9);
 
root.left.right.left = newNode(10);
root.left.right.right = newNode(11);
 
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.left.left = newNode(12);
root.right.left.right = newNode(13);
root.right.right.left = newNode(14);
root.right.right.right = newNode(15);
 
/*
            1
        /     \
       2       3
     /  \     /  \
    4   5     6    7
   /\  / \   / \  / \
  8 9 10 11 12 13 14 15     
                           */
 
    // update all the suitable_children
    // keys of all the nodes in O( N )
 
    console.log("Disconnect node"
         , findNode(root, 5, 6, 15).key
         , "from the tree");
 
// This code is contributed by akashish__

Output:

Disconnect node 3 from the tree

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!