Given a Binary Tree with distinct nodes. Given two nodes node1 and node2, check if the two nodes lies in the same subtree of the root node. That is, either of the left and right subtrees of the root node.
For Example: In the above binary tree, node 3 and 8 are in the same subtree but 4 and 5 are in different subtree.
Prerequisite: Check if a node exist in Binary Tree.
The idea is similar of searching a node in Binary Tree. There are four different cases:
- If both node1 and node2 are in left subtree of root node.
- If both node1 and node2 are in right subtree of the root node.
- If node1 is in the left subtree of the root node and node2 is in the right subtree of root node.
- If node1 is in the right subtree of the root node and node2 is in the left subtree of root node.
Use the approach of searching a node in Binary Tree and check if any of the first two cases listed above is True. If any of the first two cases listed above is found True then print YES otherwise print NO.
Below is the implementation of the above approach:
C++
// C++ program to check if two nodes// are in same subtrees of the root node#include <iostream>using namespace std;// Binary tree nodestruct 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 treebool 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 nodebool 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 Codeint 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 Codeif __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 nodeclass 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> |
Output
YES
Complexity Analysis:
- Time Complexity: O(N), as we are using recursion to traverse N nodes of the tree for checking if the nodes exists. Where N is the number of nodes in the tree.
- Auxiliary Space: O(N), as though we are not using any explicit extra space but as we are using recursion a recursive call stack will be used which will cost O (N) space.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
