Compruebe si dos Nodes están en el mismo subárbol del Node raíz

Posted on by Rudeus Greyrat

Dado un árbol binario con Nodes distintos. Dados dos Nodes node1 y node2 , verifique si los dos Nodes se encuentran en el mismo subárbol del Node raíz. Es decir, cualquiera de los subárboles izquierdo y derecho del Node raíz.
 

Por ejemplo : en el árbol binario anterior, los Nodes 3 y 8 están en el mismo subárbol pero 4 y 5 están en diferentes subárboles.
 

Requisito previo : compruebe si existe un Node en el árbol binario .
La idea es similar a buscar un Node en Binary Tree. Hay cuatro casos diferentes: 
 

  1. Si tanto el Node 1 como el Node 2 están en el subárbol izquierdo del Node raíz.
  2. Si tanto el Node 1 como el Node 2 están en el subárbol derecho del Node raíz.
  3. Si el Node1 está en el subárbol izquierdo del Node raíz y el Node2 está en el subárbol derecho del Node raíz.
  4. Si el Node1 está en el subárbol derecho del Node raíz y el Node2 está en el subárbol izquierdo del Node raíz.

Utilice el enfoque de buscar un Node en Binary Tree y verifique si alguno de los dos primeros casos enumerados anteriormente es Verdadero. Si alguno de los dos primeros casos enumerados anteriormente es Verdadero, escriba SÍ; de lo contrario, escriba NO.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to check if two nodes
// are in same subtrees of the root node
 
#include <iostream>
using namespace std;
 
// Binary tree node
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
// Function to traverse the tree in preorder
// and check if the given node exists in
// a binary tree
bool ifNodeExists(struct Node* node, int key)
{
    if (node == NULL)
        return false;
 
    if (node->data == key)
        return true;
 
    /* then recur on left subtree */
    bool res1 = ifNodeExists(node->left, key);
 
    /* now recur on right subtree */
    bool res2 = ifNodeExists(node->right, key);
 
    return res1 || res2;
}
 
// Function to check if the two given nodes
// are in same subtrees of the root node
bool ifSameSubTree(Node* root, int node1, int node2)
{
    if (root == NULL)
       return false;
 
    // CASE 1: If both nodes are in left subtree
    if (ifNodeExists(root->left, node1)
        && ifNodeExists(root->left, node2)) {
        return true;
    }
 
    // CASE 2: If both nodes are in right subtree
    else if (ifNodeExists(root->right, node1)
             && ifNodeExists(root->right, node2)) {
        return true;
    }
 
    // CASE 3 and 4: Nodes are in different subtrees
    else
        return false;
}
 
// Driver Code
int main()
{
    struct Node* root = new Node(0);
    root->left = new Node(1);
    root->left->left = new Node(3);
    root->left->left->left = new Node(7);
    root->left->right = new Node(4);
    root->left->right->left = new Node(8);
    root->left->right->right = new Node(9);
    root->right = new Node(2);
    root->right->left = new Node(5);
    root->right->right = new Node(6);
 
    int node1 = 3, node2 = 8;
 
    if (ifSameSubTree(root, node1, node2))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

Java

// Java program to check if two nodes
// are in same subtrees of the root node
import java.util.*;
class solution
{
 
// Binary tree node
 static class Node {
    int data;
     Node left, right;
    Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
// Function to traverse the tree in preorder
// and check if the given node exists in
// a binary tree
static boolean ifNodeExists( Node node, int key)
{
    if (node == null)
        return false;
 
    if (node.data == key)
        return true;
 
    /* then recur on left subtree */
    boolean res1 = ifNodeExists(node.left, key);
 
    /* now recur on right subtree */
    boolean res2 = ifNodeExists(node.right, key);
 
    return res1 || res2;
}
 
// Function to check if the two given nodes
// are in same subtrees of the root node
static boolean ifSameSubTree(Node root, int node1, int node2)
{
    if (root == null)
    return false;
 
    // CASE 1: If both nodes are in left subtree
    if (ifNodeExists(root.left, node1)
        && ifNodeExists(root.left, node2)) {
        return true;
    }
 
    // CASE 2: If both nodes are in right subtree
    else if (ifNodeExists(root.right, node1)
            && ifNodeExists(root.right, node2)) {
        return true;
    }
 
    // CASE 3 and 4: Nodes are in different subtrees
    else
        return false;
}
 
// Driver Code
public static void main(String args[])
{
     Node root = new Node(0);
    root.left = new Node(1);
    root.left.left = new Node(3);
    root.left.left.left = new Node(7);
    root.left.right = new Node(4);
    root.left.right.left = new Node(8);
    root.left.right.right = new Node(9);
    root.right = new Node(2);
    root.right.left = new Node(5);
    root.right.right = new Node(6);
 
    int node1 = 3, node2 = 8;
 
    if (ifSameSubTree(root, node1, node2))
        System.out.println("YES");
    else
        System.out.println( "NO");
 
}
}
//contributed by Arnab Kundu

Python3

"""Python3 program to check if two nodes
are in same subtrees of the root node """
 
# A Binary Tree Node
# Utility function to create a
# new tree node
class newNode:
 
    # Constructor to create a newNode
    def __init__(self, data):
        self.data= data
        self.left = None
        self.right = None
        self.visited = False
 
# Function to traverse the tree in
# preorder and check if the given
# node exists in a binary tree
def ifNodeExists(node, key) :
    if (node == None):
        return False
 
    if (node.data == key):
        return True
 
    """ then recur on left subtree """
    res1 = ifNodeExists(node.left, key)
 
    """ now recur on right subtree """
    res2 = ifNodeExists(node.right, key)
 
    return res1 or res2
 
# Function to check if the two given nodes
# are in same subtrees of the root node
def ifSameSubTree(root, node1, node2):
 
    if (root == None) :
        return False
 
    # CASE 1: If both nodes are in
    # left subtree
    if (ifNodeExists(root.left, node1)
        and ifNodeExists(root.left, node2)):
        return True
 
    # CASE 2: If both nodes are in
    # right subtree
    elif (ifNodeExists(root.right, node1)
            and ifNodeExists(root.right, node2)):
        return True
     
    # CASE 3 and 4: Nodes are in
    # different subtrees
    else:
        return False
                         
# Driver Code
if __name__ == '__main__':
    root = newNode(0)
    root.left = newNode(1)
    root.left.left = newNode(3)
    root.left.left.left = newNode(7)
    root.left.right = newNode(4)
    root.left.right.left = newNode(8)
    root.left.right.right = newNode(9)
    root.right = newNode(2)
    root.right.left = newNode(5)
    root.right.right = newNode(6)
 
    node1 = 3
    node2 = 8
 
    if (ifSameSubTree(root, node1, node2)):
        print("YES")
    else:
        print("NO")
 
# This code is contributed by
# SHUBHAMSINGH10

C#

// C# program to check if two nodes
// are in same subtrees of the root node
using System;
 
class GFG
{
 
// Binary tree node
class Node
{
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
// Function to traverse the tree in preorder
// and check if the given node exists in
// a binary tree
static bool ifNodeExists( Node node, int key)
{
    if (node == null)
        return false;
 
    if (node.data == key)
        return true;
 
    /* then recur on left subtree */
    bool res1 = ifNodeExists(node.left, key);
 
    /* now recur on right subtree */
    bool res2 = ifNodeExists(node.right, key);
 
    return res1 || res2;
}
 
// Function to check if the two given nodes
// are in same subtrees of the root node
static bool ifSameSubTree(Node root,
                int node1, int node2)
{
    if (root == null)
    return false;
 
    // CASE 1: If both nodes are in left subtree
    if (ifNodeExists(root.left, node1)
        && ifNodeExists(root.left, node2))
    {
        return true;
    }
 
    // CASE 2: If both nodes are in right subtree
    else if (ifNodeExists(root.right, node1)
            && ifNodeExists(root.right, node2))
    {
        return true;
    }
 
    // CASE 3 and 4: Nodes are in different subtrees
    else
        return false;
}
 
// Driver Code
public static void Main()
{
    Node root = new Node(0);
    root.left = new Node(1);
    root.left.left = new Node(3);
    root.left.left.left = new Node(7);
    root.left.right = new Node(4);
    root.left.right.left = new Node(8);
    root.left.right.right = new Node(9);
    root.right = new Node(2);
    root.right.left = new Node(5);
    root.right.right = new Node(6);
 
    int node1 = 3, node2 = 8;
 
    if (ifSameSubTree(root, node1, node2))
        Console.WriteLine("YES");
    else
        Console.WriteLine( "NO");
 
}
}
 
/* This code is contributed by Rajput-Ji*/

Javascript

<script>
 
// JavaScript program to check if two nodes
// are in same subtrees of the root node
 
    // Binary tree node
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}
 
    // Function to traverse the tree in preorder
    // and check if the given node exists in
    // a binary tree
    function ifNodeExists(node , key) {
        if (node == null)
            return false;
 
        if (node.data == key)
            return true;
 
        /* then recur on left subtree */
        var res1 = ifNodeExists(node.left, key);
 
        /* now recur on right subtree */
        var res2 = ifNodeExists(node.right, key);
 
        return res1 || res2;
    }
 
    // Function to check if the two given nodes
    // are in same subtrees of the root node
    function ifSameSubTree(root , node1 , node2) {
        if (root == null)
            return false;
 
        // CASE 1: If both nodes are in left subtree
        if (ifNodeExists(root.left, node1) &&
        ifNodeExists(root.left, node2)) {
            return true;
        }
 
        // CASE 2: If both nodes are in right subtree
        else if (ifNodeExists(root.right, node1) &&
        ifNodeExists(root.right, node2)) {
            return true;
        }
 
        // CASE 3 and 4: Nodes are in different subtrees
        else
            return false;
    }
 
    // Driver Code
     
        var root = new Node(0);
        root.left = new Node(1);
        root.left.left = new Node(3);
        root.left.left.left = new Node(7);
        root.left.right = new Node(4);
        root.left.right.left = new Node(8);
        root.left.right.right = new Node(9);
        root.right = new Node(2);
        root.right.left = new Node(5);
        root.right.right = new Node(6);
 
        var node1 = 3, node2 = 8;
 
        if (ifSameSubTree(root, node1, node2))
            document.write("YES");
        else
            document.write("NO");
 
// This code is contributed by todaysgaurav
 
</script>
Producción: 

YES

 

Complejidad de tiempo: O (N), ya que estamos usando recursividad para atravesar N Nodes del árbol para verificar si existen los Nodes. Donde N es el número de Nodes en el árbol.

Espacio auxiliar: O (N), como si no estuviéramos usando ningún espacio adicional explícito, pero como estamos usando recursividad, se usará una pila de llamadas recursivas que costará O (N) espacio.

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *