Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

0 0 9 minutes read

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T.

For Example:

Input:
Tree T - 
         1            
       /   \         
      2     3
    /  \   /  \  
   4   5  6    7

Tree S - 
      2
    /  \  
   4    5
Output: YES
Explanation:
The above tree is the subtree of the tree T,
Hence the output is YES

Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each node of the tree that Pre-order traversal of that tree is the same as the Pre-order Traversal of the tree S with taking care of Null values that is by including the Null values in the Traversal list, because if the null values are not taken care then two different trees can have same pre-order traversal. Such as in the case of below trees –

    1           1
   /  \        /  \
  2    N      N    2  
 / \              / \
N   N            N   N

Pre-order Traversal of both the trees will be -
{1, 2} - In case of without taking care of null values
{1, 2, N, N, N} and {1, N, 2, N, N}
In case of taking care of null values.

Algorithm:

Declare a stack, to keep track of the left and right child of the nodes.
Push the root node of the tree T.
Run a loop while the stack is not empty and then check that if the pre-order traversal of the top node of the stack is the same, then return true.
If the pre-order traversal does not match with the tree then pop the top node from the stack and push its left and right child of the popped node.

Below is the implementation of the above approach:

C++

// C++ implementation to check
// if a tree is a subtree of 
// another binary tree
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of the 
// binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
 
// Function to create 
// new node 
Node* newNode(int x)
{
    Node* temp = (Node*)malloc(
                   sizeof(Node));
    temp->data = x;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
// Function to check if two trees
// have same pre-order traversal
bool areTreeIdentical(Node* t1, Node* t2)
{
    stack<Node*> s1;
    stack<Node*> s2;
    Node* temp1;
    Node* temp2;
    s1.push(t1);
    s2.push(t2);
     
    // Loop to iterate over the stacks
    while (!s1.empty() && !s2.empty()) {
        temp1 = s1.top();
        temp2 = s2.top();
        s1.pop();
        s2.pop();
        // Both are None 
        // hence they are equal
        if (temp1 == NULL && 
            temp2 == NULL)
            continue;
         
        // nodes are unequal
        if ((temp1 == NULL && temp2 != NULL) || 
           (temp1 != NULL && temp2 == NULL))
            return false;
         
        // nodes have unequal data
        if (temp1->data != temp2->data)
            return false;
 
        s1.push(temp1->right);
        s2.push(temp2->right);
 
        s1.push(temp1->left);
        s2.push(temp2->left);
    }
    // if both tree are identical 
    // both stacks must be empty.
    if (s1.empty() && s2.empty())
        return true;
    else
        return false;
}
// Function to check if the Tree s
// is the subtree of the Tree T
bool isSubTree(Node* s, Node* t)
{
    // first we find the root of s in t
    // by traversing in pre order fashion
    stack<Node*> stk;
    Node* temp;
    stk.push(t);
    while (!stk.empty()) {
        temp = stk.top();
        stk.pop();
        // if current node data is equal
        // to root of s then
        if (temp->data == s->data) {
            if (areTreeIdentical(s, temp))
                return true;
        }
        if (temp->right)
            stk.push(temp->right);
        if (temp->left)
            stk.push(temp->left);
    }
    return false;
}
 
// Driver Code
int main()
{
    /*
            1
           / \
          2      3
         / \ / \
        4  5 6  7
    */
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    /*
         2
        / \
       4   5
    */
 
    Node* root2 = newNode(2);
    root2->left = newNode(4);
    root2->right = newNode(5);
    if (isSubTree(root2, root))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Java

// Java implementation to check
// if a tree is a subtree of 
// another binary tree
import java.util.*;
 
class GFG{
  
// Structure of the 
// binary tree node
static class Node {
    int data;
    Node left;
    Node right;
};
  
// Function to create 
// new node 
static Node newNode(int x)
{
    Node temp = new Node();
    temp.data = x;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// Function to check if two trees
// have same pre-order traversal
static boolean areTreeIdentical(Node t1, Node t2)
{
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    Node temp1;
    Node temp2;
    s1.add(t1);
    s2.add(t2);
      
    // Loop to iterate over the stacks
    while (!s1.isEmpty() && !s2.isEmpty()) {
        temp1 = s1.peek();
        temp2 = s2.peek();
        s1.pop();
        s2.pop();
 
        // Both are None 
        // hence they are equal
        if (temp1 == null && 
            temp2 == null)
            continue;
          
        // nodes are unequal
        if ((temp1 == null && temp2 != null) || 
           (temp1 != null && temp2 == null))
            return false;
          
        // nodes have unequal data
        if (temp1.data != temp2.data)
            return false;
  
        s1.add(temp1.right);
        s2.add(temp2.right);
  
        s1.add(temp1.left);
        s2.add(temp2.left);
    }
 
    // if both tree are identical 
    // both stacks must be empty.
    if (s1.isEmpty() && s2.isEmpty())
        return true;
    else
        return false;
}
// Function to check if the Tree s
// is the subtree of the Tree T
static boolean isSubTree(Node s, Node t)
{
    // first we find the root of s in t
    // by traversing in pre order fashion
    Stack<Node> stk = new Stack<Node>();
    Node temp;
    stk.add(t);
    while (!stk.isEmpty()) {
        temp = stk.peek();
        stk.pop();
 
        // if current node data is equal
        // to root of s then
        if (temp.data == s.data) {
            if (areTreeIdentical(s, temp))
                return true;
        }
        if (temp.right != null)
            stk.add(temp.right);
        if (temp.left != null)
            stk.add(temp.left);
    }
    return false;
}
  
// Driver Code
public static void main(String[] args)
{
    /*
            1
           / \
          2      3
         / \ / \
        4  5 6  7
    */
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.left = newNode(6);
    root.right.right = newNode(7);
    /*
         2
        / \
       4   5
    */
  
    Node root2 = newNode(2);
    root2.left = newNode(4);
    root2.right = newNode(5);
    if (isSubTree(root2, root))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation to check
# if a tree is a subtree of
# another binary tree
 
# Structure of the
# binary tree node
class Node:
   
    def __init__(self, data):
       
        self.data = data
        self.left = None
        self.right = None
 
# Function to check if two trees
# have same pre-order traversal
def areTreeIdentical(t1 : Node, 
                     t2 : Node) -> bool:
    s1 = []
    s2 = []
    s1.append(t1)
    s2.append(t2)
 
    # Loop to iterate 
    # over the stacks
    while s1 and s2:
        temp1 = s1.pop()
        temp2 = s2.pop()
         
        # Both are None
        # hence they are equal
        if (temp1 is None and
            temp2 is None):
            continue
 
        # Nodes are unequal
        if ((temp1 is None and
             temp2 is not None) or
            (temp1 is not None and
             temp2 is None)):
            return False
 
        # Nodes have unequal data
        if (temp1.data != temp2.data):
            return False
 
        s1.append(temp1.right)
        s2.append(temp2.right)
 
        s1.append(temp1.left)
        s2.append(temp2.left)
 
    # If both tree are identical
    # both stacks must be empty.
    if s1 and s2:
        return False
    return True
 
# Function to check if the Tree s
# is the subtree of the Tree T
def isSubTree(s : Node, 
              t : Node) -> Node:
 
    # First we find the 
    # root of s in t
    # by traversing in 
    # pre order fashion
    stk = []
    stk.append(t)
     
    while stk:
        temp = stk.pop()
         
        # If current node data is equal
        # to root of s then
        if (temp.data == s.data):
            if (areTreeIdentical(s, temp)):
                return True
        if (temp.right):
            stk.append(temp.right)
        if (temp.left):
            stk.append(temp.left)
             
    return False
 
# Driver Code
if __name__ == "__main__":
   
    '''
            1
           / \
          2      3
         / \ / \
        4  5 6  7
    '''
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
     
    '''
         2
        / \
       4   5
    '''
    root2 = Node(2)
    root2.left = Node(4)
    root2.right = Node(5)
    if (isSubTree(root2, root)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by sanjeev2552

C#

// C# implementation to check
// if a tree is a subtree of 
// another binary tree
using System;
using System.Collections.Generic;
 
class GFG{
   
// Structure of the 
// binary tree node
class Node {
    public int data;
    public Node left;
    public Node right;
};
   
// Function to create 
// new node 
static Node newNode(int x)
{
    Node temp = new Node();
    temp.data = x;
    temp.left = null;
    temp.right = null;
    return temp;
}
  
// Function to check if two trees
// have same pre-order traversal
static bool areTreeIdentical(Node t1, Node t2)
{
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    Node temp1;
    Node temp2;
    s1.Push(t1);
    s2.Push(t2);
       
    // Loop to iterate over the stacks
    while (s1.Count != 0 && s2.Count != 0) {
        temp1 = s1.Peek();
        temp2 = s2.Peek();
        s1.Pop();
        s2.Pop();
  
        // Both are None 
        // hence they are equal
        if (temp1 == null && 
            temp2 == null)
            continue;
           
        // nodes are unequal
        if ((temp1 == null && temp2 != null) || 
           (temp1 != null && temp2 == null))
            return false;
           
        // nodes have unequal data
        if (temp1.data != temp2.data)
            return false;
   
        s1.Push(temp1.right);
        s2.Push(temp2.right);
   
        s1.Push(temp1.left);
        s2.Push(temp2.left);
    }
  
    // if both tree are identical 
    // both stacks must be empty.
    if (s1.Count == 0 && s2.Count == 0)
        return true;
    else
        return false;
}
 
// Function to check if the Tree s
// is the subtree of the Tree T
static bool isSubTree(Node s, Node t)
{
    // first we find the root of s in t
    // by traversing in pre order fashion
    Stack<Node> stk = new Stack<Node>();
    Node temp;
    stk.Push(t);
    while (stk.Count != 0) {
        temp = stk.Peek();
        stk.Pop();
  
        // if current node data is equal
        // to root of s then
        if (temp.data == s.data) {
            if (areTreeIdentical(s, temp))
                return true;
        }
        if (temp.right != null)
            stk.Push(temp.right);
        if (temp.left != null)
            stk.Push(temp.left);
    }
    return false;
}
   
// Driver Code
public static void Main(String[] args)
{
    /*
            1
           / \
          2      3
         / \ / \
        4  5 6  7
    */
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.left = newNode(6);
    root.right.right = newNode(7);
    /*
         2
        / \
       4   5
    */
   
    Node root2 = newNode(2);
    root2.left = newNode(4);
    root2.right = newNode(5);
    if (isSubTree(root2, root))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
  
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript implementation to check
// if a tree is a subtree of 
// another binary tree
 
// Structure of the 
// binary tree node
class Node 
{
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
   
// Function to create 
// new node 
function newNode(x)
{
    var temp = new Node();
    temp.data = x;
    temp.left = null;
    temp.right = null;
    return temp;
}
  
// Function to check if two trees
// have same pre-order traversal
function areTreeIdentical(t1, t2)
{
    var s1 = [];
    var s2 = [];
    var temp1 = null;
    var temp2 = null;
    s1.push(t1);
    s2.push(t2);
       
    // Loop to iterate over the stacks
    while (s1.length != 0 && s2.length != 0)
    {
        temp1 = s1[s1.length - 1];
        temp2 = s2[s2.length - 1];
        s1.pop();
        s2.pop();
  
        // Both are None 
        // hence they are equal
        if (temp1 == null && 
            temp2 == null)
            continue;
           
        // Nodes are unequal
        if ((temp1 == null && temp2 != null) || 
           (temp1 != null && temp2 == null))
            return false;
           
        // Nodes have unequal data
        if (temp1.data != temp2.data)
            return false;
   
        s1.push(temp1.right);
        s2.push(temp2.right);
   
        s1.push(temp1.left);
        s2.push(temp2.left);
    }
  
    // If both tree are identical 
    // both stacks must be empty.
    if (s1.length == 0 && s2.length == 0)
        return true;
    else
        return false;
}
 
// Function to check if the Tree s
// is the subtree of the Tree T
function isSubTree(s, t)
{
     
    // First we find the root of s in t
    // by traversing in pre order fashion
    var stk = [];
    var temp;
    stk.push(t);
     
    while (stk.length != 0)
    {
        temp = stk[stk.length - 1];
        stk.pop();
  
        // If current node data is equal
        // to root of s then
        if (temp.data == s.data) 
        {
            if (areTreeIdentical(s, temp))
                return true;
        }
        if (temp.right != null)
            stk.push(temp.right);
        if (temp.left != null)
            stk.push(temp.left);
    }
    return false;
}
   
// Driver Code
/*
        1
       / \
      2   3
     / \ / \
    4  5 6  7
*/
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.left = newNode(6);
root.right.right = newNode(7);
/*
     2
    / \
   4   5
*/
 
var root2 = newNode(2);
root2.left = newNode(4);
root2.right = newNode(5);
 
if (isSubTree(root2, root))
    document.write("Yes");
else
    document.write("No");
     
// This code is contributed by rutvik_56
 
</script>

Output:

Yes

Time complexity: O(N) where N is no of nodes in a binary tree

Auxiliary Space: O(N)

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!