Check if a binary tree is subtree of another binary tree
Given two binary trees T and S, check whether tree S has exactly the same structure and node values with a subtree of T, i.e., check if tree S is a subtree of the tree T.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow. The first line of each test case contains elements of the first tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. The second line of each test case contains elements of the second tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. For example, the input for the tree depicted in the below image would be:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation:

Level 1: The root node of the tree is 1 Level 2: Left child of 1 = 2 Right child of 1 = 3 Level 3: Left child of 2 = 4 Right child of 2 = null (-1) Left child of 3 = 5 Right child of 3 = 6 Level 4: Left child of 4 = null (-1) Right child of 4 = 7 Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 6 = null (-1) Right child of 6 = null (-1) Level 5: Left child of 7 = null (-1) Right child of 7 = null (-1) The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are null(-1).

Note:

The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, the only line of output prints true if tree S is a subtree of the tree T else prints false. The output for each test case is in a separate line.

Note:

You do not need to print anything; it has already been taken care of.

Constraints:

1

Question

Check if a binary tree is subtree of another binary tree

Given two binary trees T and S, check whether tree S has exactly the same structure and node values with a subtree of T, i.e., check if tree S is a subtree of the tree T.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains elements of the first tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

The second line of each test case contains elements of the second tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be:

example

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation:

Level 1:
The root node of the tree is 1

Level 2:
Left child of 1 = 2
Right child of 1 = 3

Level 3:
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4:
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5:
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).

Note:

The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, the only line of output prints true if tree S is a subtree of the tree T else prints false.

The output for each test case is in a separate line.

Note:

You do not need to print anything; it has already been taken care of.

Constraints:

1 <= T <= 100
1 <= N, M <= 1000
0 <= data <= 10^6 and data != -1

Where ‘T’ is the number of test cases, ‘N’ and ‘M’ are the number of nodes in the given binary trees’, and “data” is the value of the binary tree node.

Time Limit: 1 sec.

Accepted Answer

The recursive approach would be to traverse the tree T in preorder fashion. For every visited node in the traversal, see if the subtree rooted with this node is identical to S.
Time worst-case complexity is O(mn) where m and n are number of nodes in given two trees.
Auxiliary space : O(n)

The above approach can be optimised to O(n) time complexity. The idea is based on the fact that inorder and preorder/postorder uniquely identify a binary tree. Tree S is a subtree of T if both inorder and preorder traversals of S arew substrings of inorder and preorder traversals of T respectively.
Steps :
1) Find inorder and preorder traversals of T, store them in two auxiliary arrays inT[] and preT[].
2) Find inorder and preorder traversals of S, store them in two auxiliary arrays inS[] and preS[].
3) If inS[] is a subarray of inT[] and preS[] is a subarray preT[], then S is a subtree of T. Else not.

Accepted Answer

Comparison of Nodes

Traverse the tree T in preorder fashion and treat every node of the given tree T as the root, treat it as a subtree and compare the corresponding subtree with the given subtree S for equality. For checking the equality, we can compare all the nodes of the two subtrees.

So the basic idea is to traverse over the given tree T and treat every node as the root of the subtree currently being considered and compare the corresponding subtree with the given subtree S for equality. To check the equality of the two subtrees, we make use of areIdentical(t,s) function, which takes t and s, which are roots of the two subtrees to be compared as the inputs and returns “true” or “false” depending on whether the two are equal or not. It compares all the nodes of the two subtrees for equality. Firstly, it checks the roots of the two trees for equality and then calls itself recursively for the left subtree and the right subtree.

Space Complexity: O(1)Explanation:

O(N), Where ‘N’ is the number of nodes in the given binary tree ‘T’.

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion tree, and the height of a skewed binary tree could be ‘N’ in the worst case.

Time Complexity: O(1)Explanation:

O(M * N), where ‘M’ and ‘N’ are the number of nodes in the given binary trees.

Since in the worst case (Skewed Trees), we might be visiting all the nodes of the ‘S’ binary tree for each node of the ‘T’ binary tree. So, the overall time complexity will be O(M * N).

Java (SE 1.8)

/*
    Time complexity: O(M * N)
    Space complexity: O(N)

    where 'M' and 'N' are the number of nodes in the given binary trees.
*/

public class Solution {

    // Function to check whether trees with roots as t and s are identical or not.
    private static boolean areIdentical(TreeNode t, TreeNode s) {

        // Base cases.
        if (t == null && s == null) {
            return true;
        }

        if (t == null || s == null) {
            return false;
        }

        // Check if the data of both roots is same and data of left and right subtrees are also same.
        return ((int)t.val == (int)s.val && areIdentical(t.left, s.left) && areIdentical(t.right, s.right));
    }

    // This function returns true if S is a subtree of T, otherwise false.
    public static boolean isSubtree(TreeNode T, TreeNode S) {
        
        // Base cases.
        if (S == null) {
            return true;
        }

        if (T == null) {
            return false;
        }

        // Check the tree with root as current node.
        if (areIdentical(T, S)) {
            return true;
        }

        // Check for left and right subtrees one by one.
        return isSubtree(T.left, S) || isSubtree(T.right, S);
    }
}

C++ (g++ 5.4)

/*
    Time complexity: O(M * N)
    Space complexity: O(N)

    where 'M' and 'N' are the number of nodes in the given binary trees.
*/

// Function to check whether trees with roots as t and s are identical or not.
bool areIdentical(TreeNode *t, TreeNode *s)
{

    // Base cases.
    if (t == NULL && s == NULL)
    {
        return true;
    }

    if (t == NULL || s == NULL)
    {
        return false;
    }

    // Check if the data of both roots is same and data of left and right subtrees are also same.
    return (t->val == s->val && areIdentical(t->left, s->left) && areIdentical(t->right, s->right));
}

// This function returns true if S is a subtree of T, otherwise false.
bool isSubtree(TreeNode *T, TreeNode *S)
{
    // Base cases.
    if (S == NULL)
    {
        return true;
    }

    if (T == NULL)
    {
        return false;
    }

    // Check the tree with root as current node.
    if (areIdentical(T, S))
    {
        return true;
    }

    // Check for left and right subtrees one by one.
    return isSubtree(T->left, S) || isSubtree(T->right, S);
}

Python (3.5)

'''
	Time complexity: O(M * N)
	Space complexity: O(N)

	where M and N are the number of nodes in the given binary trees.
'''

'''
    Following is the TreeNode Structure

    class BinaryTreeNode:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None

'''

# Function to check whether trees with roots as t and s are identical or not.
def areIdentical(t, s):

    # Base cases.
    if (t == None and s == None):
        return True

    if (t == None or s == None):
        return False

    # Check if the data of both roots is same and data of left and right subtrees are also same.
    return (t.data == s.data and areIdentical(t.left, s.left) and areIdentical(t.right, s.right))


# This function returns true if S is a subtree of T, otherwise false.
def isSubtree(T, S):

    # Base cases.
    if (S == None):
        return True

    if (T == None):
        return False

    # Check the tree with root as current node.
    if (areIdentical(T, S)):
        return True

    # Check for left and right subtrees one by one.
    return isSubtree(T.left, S) or isSubtree(T.right, S)

Accepted Answer

Using Inorder and Postorder

We know that inorder and preorder/postorder identify a tree uniquely. The idea is to store inorder and postorder traversal of both trees in separate arrays. Then, for a given binary tree S to be a subset of another binary tree T, the inorder traversal of S should be a subset of inorder traversal of T. Similarly, the post-order traversal of S should be a subset of post-order traversal of T. We can also perform pre-order traversal instead of post-order traversal. For example, consider the below trees:

Inorder(T) = {4, 2, 5, 1, 6, 3, 7}

Inorder(S) = {6, 3, 7}

Postorder(T) = {4, 5, 2, 6, 7, 3, 1}

Postorder(S) = {6, 7, 3}

Since inorder(S) is a subset of inorder(T) and postorder(S) is a subset of postorder(T), we can say that S is a subtree of T.

To check whether the inorder(S)/postorder(S) is a subset of inorder(T)/postorder(T) or not, we will use the naive algorithm, i.e., store the inorder and postorder traversal of both the trees in string. Then, use String.contains() function to check if the inorder/postorder of tree ‘S’ is substring of inorder/postorder of tree ‘T’ or not.

Space Complexity: O(1)Explanation:

O(N), Where ‘N’ is the number of nodes in the given binary tree ‘T’.

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion tree, and the height of a skewed binary tree could be ‘N’ in the worst case.

Time Complexity: O(1)Explanation:

O(M * N), where ‘M’ and ‘N’ are the number of nodes in the given binary trees.

Time complexities of the functions we have used:

To find inorder/postorder: In the worst case, to find the inorder/postorder traversal of a binary tree, we have to traverse ‘N’ nodes where ‘N’ is the number of nodes in the tree.
String.contains(): A naive implementation of this function might take (N + 1 - M) * M comparisons to decide that a given string of length ‘N’ does not contain a particular substring of length ‘M’. That’s O(M * N) for the worst case.

So, the overall time complexity will be O(M * N).

C++ (g++ 5.4)

/*
    Time complexity: O(M * N)
    Space complexity: O(N)

    where 'M' and 'N' are the number of nodes in the given binary trees.
*/

#include 

// Function to return in-order traversal of the tree in a string.
string inorder(TreeNode *node)
{
    // Base case.
    if (node == NULL)
    {
        return "NULL";
    }

    return inorder(node->left) + " " + to_string(node->val) + " " + inorder(node->right);
}

// Function to return post-order traversal of the tree in a string.
string postorder(TreeNode *node)
{
    // Base case.
    if (node == NULL)
    {
        return "NULL";
    }

    return postorder(node->left) + " " + postorder(node->right) + " " + to_string(node->val);
}

// This function returns true if S is a subtree of T, otherwise false.
bool isSubtree(TreeNode *T, TreeNode *S)
{
    // Base case: both trees are same.
    if (T == S)
    {
        return true;
    }

    // Base case: if first tree is empty but second tree is non-empty.
    if (T == NULL)
    {
        return false;
    }

    // Store in-order traversal of both trees in Tin and Sin respectively.
    string Tin = inorder(T);
    string Sin = inorder(S);

    // Return false if Sin string is not a substring of Tin string.
   
    if (Tin.find(Sin) == string::npos) {
      return false;
    }

    // Store post-order traversal of both trees in Tpost and Spost respectively.
    string Tpost = postorder(T);
    string Spost = postorder(S);
    
    // Return false if Spost string is not a substring of Tpost string.
    
    if (Tpost.find(Spost) == string::npos) {
      return false;
    }

    return true;
}

Java (SE 1.8)

/*
	Time complexity: O(M * N)
	Space complexity: O(N)

	where 'M' and 'N' are the number of nodes in the given binary trees.
*/

public class Solution {

	// Function to return in-order traversal of the tree in a string.
	private static String inorder(TreeNode node) {

        // Base case.
		if (node == null) {
			return null;
		}

		return inorder(node.left) + " " + String.valueOf(node.val) + " " + inorder(node.right);
	}

	// Function to return post-order traversal of the tree in a string.
	private static String postorder(TreeNode node) {

        // Base case.
		if (node == null) {
			return null;
		}

		return postorder(node.left) + " " + postorder(node.right) + " " + String.valueOf(node.val);
	}

	// This function returns true if S is a subtree of T, otherwise false.
	public static boolean isSubtree(TreeNode T, TreeNode S) {

		// Base case: both trees are same.
		if (T == S) {
			return true;
		}

		// Base case: if first tree is empty but second tree is non-empty.
		if (T == null) {
			return false;
		}

		// Store in-order traversal of both trees in Tin and Sin respectively.
		String Tin = inorder(T);
		String Sin = inorder(S);

		// Return false if Sin string is not a substring of Tin string.
		if(!Tin.contains(Sin)) {
			return false;
		}

		// Store post-order traversal of both trees in Tpost and Spost respectively.
		String Tpost = postorder(T);
		String Spost = postorder(S);

		// Return false if Spost string is not a substring of Tpost string.
		if (!Tpost.contains(Spost)) {
			return false;
		}

		return true;
	}
}

Python (3.5)

'''
	Time complexity: O(M * N)
	Space complexity: O(N)

	where M and N are the number of nodes in the given binary trees.
'''

'''
  Following is the TreeNode Structure

    class BinaryTreeNode:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None

'''

# Function to return in-order traversal of the tree in a string.
def inorder(node):

    # Base case.
    if (node == None):
        return "NULL"

    return inorder(node.left) + " " + str(node.data) + " " + inorder(node.right)


# Function to return post-order traversal of the tree in a string.
def postorder(node):

    # Base case.
    if (node == None):
        return "NULL"

    return postorder(node.left) + " " + postorder(node.right) + " " + str(node.data)


# This function returns true if S is a subtree of T, otherwise false.
def isSubtree(T, S):

    # Base case: both trees are same.
    if (T == S):
        return True

    # Base case: if first tree is empty but second tree is non-empty.
    if (T == None):
        return False

    # Store in-order traversal of both trees in Tin and Sin respectively.
    Tin = inorder(T)
    Sin = inorder(S)

    # Return false if Sin string is not a substring of Tin string.
    if (Tin.find(Sin) == -1):
      return False

    # Store post-order traversal of both trees in Tpost and Spost respectively.
    Tpost = postorder(T)
    Spost = postorder(S)
    
    # Return false if Spost string is not a substring of Tpost string.
    if (Tpost.find(Spost) == -1):
      return False

    return True

Accepted Answer

Using KMP algorithm

We know that inorder and preorder/postorder identify a tree uniquely. The idea is to store inorder and postorder traversal of both trees in separate arrays. Then, for a given binary tree S to be a subset of another binary tree T, the inorder traversal of S should be a subset of inorder traversal of T. Similarly, the post-order traversal of S should be a subset of the post-order traversal of T. We can also perform pre-order traversal instead of post-order traversal. For example, consider the below trees:

Inorder(T) = {4, 2, 5, 1, 6, 3, 7}

Inorder(S) = {6, 3, 7}

Postorder(T) = {4, 5, 2, 6, 7, 3, 1}

Postorder(S) = {6, 7, 3}

Since inorder(S) is a subset of inorder(T) and postorder(S) is a subset of postorder(T), we can say that S is a subtree of T.

To check whether the inorder(S)/postorder(S) is a subset of inorder(T)/postorder(T) or not, we will use the KMP algorithm, which is a pattern searching algorithm that uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst-case complexity to O(n). The basic idea behind KMP’s algorithm is, whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the next window. We take advantage of this information to avoid matching the character that we know will anyway match.

Preprocessing Overview:

KMP algorithm preprocesses pat[] and constructs an auxiliary lps[] of size m (same as the size of pattern), which is used to skip characters while matching.
Name “lps” indicates the longest proper prefix, which also suffix. A proper prefix is a prefix with the whole string not allowed. For example, prefixes of “ABC” are “”, “A”, “AB”, and “ABC”. Proper prefixes are “”, “A”, and “AB”. Suffixes of the string are “”, “C”, “BC”, and “ABC”.
We search for lps in sub-patterns. More clearly, we focus on sub-strings of patterns that are either prefix and suffix.
For each sub-pattern pat[0..i] where i = 0 to m - 1, lps[i] stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern pat[0..i]. For example, for the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3].

Searching Algorithm:

Unlike naive algorithm, where we slide the pattern by one and compare all characters at each shift, we use a value from lps[] to decide the next characters to be matched. The idea is not to match a character that we know will anyway match.

How to use lps[] to decide the next positions (or to know the number of characters to be skipped)?

We start the comparison of pat[j] with j = 0 with characters of the current window of text.
We keep matching characters txt[i] and pat[j] and keep incrementing i and j while pat[j] and txt[i] keep matching.
When we see a mismatch
- We know that characters pat[0..j-1] match with txt[i-j...i-1] (Note that j starts with 0 and increments it only when there is a match).
- We also know that lps[j - 1] is the count of characters of pat[0...j-1] that are both proper prefix and suffix.
- From the above two points, we can conclude that we do not need to match these lps[j - 1] characters with txt[i-j...i-1] because we know that these characters will anyway match.

Space Complexity: O(1)Explanation:

O(N), where ‘N’ is the number of nodes in the given binary tree ‘T’.

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion tree, and the height of a skewed binary tree could be ‘N’ in the worst case.

Time Complexity: O(1)Explanation:

O(N), where ‘N’ is the number of nodes in the given binary tree ‘T’.

Time complexities of the functions we have used:

To find inorder/postorder: In the worst case, to find the inorder/postorder traversal of a binary tree, we have to traverse ‘N’ nodes where ‘N’ is the number of nodes in the tree.
KMPSearch(): To check whether a string is a substring of another string or not, we have used the KMP algorithm, which is a pattern searching algorithm having worst-case time complexity as O(N), where ‘N’ is the size of the string.

So, the overall time complexity will be O(N).

Java (SE 1.8)

/*
	Time complexity: O(N)
	Space complexity: O(N)

	where 'N' is the number of nodes in the given binary tree 'T'.
 */

public class Solution {

	private static boolean KMPSearch(String pat, String txt) {

		int M = pat.length();
		int N = txt.length();

		// Create lps[] that will hold the longest prefix suffix values for pattern.
		int lps[] = new int[M];
		int j = 0; // index for pat[].

		// Preprocess the pattern (calculate lps[] array).
		computeLPSArray(pat, M, lps);

		// Index for txt.
		int i = 0;
		while (i < N) {
			
            if (pat.charAt(j) == txt.charAt(i)) {
				j++;
				i++;
			}

			if (j == M) {
				return true;
			}

			// Mismatch after j matches.
			else if (i < N && pat.charAt(j) != txt.charAt(i)) {

				// Do not match lps[0..lps[j-1]] characters, they will match anyway.
				if (j != 0) {
					j = lps[j - 1];
				} else {
					i++;
				}
			}
		}
		
		return false;
	}

	private static void computeLPSArray(String pat, int M, int lps[]) {

		// Length of the previous longest prefix suffix.
		int len = 0;
		int i = 1;

		// lps[0] is always 0.
		lps[0] = 0;

		// The loop calculates lps[i] for i = 1 to M-1.
		while (i < M) {

			if (pat.charAt(i) == pat.charAt(len)) {
				len++;
				lps[i] = len;
				i++;
			} else {
				if (len != 0) {
					len = lps[len - 1];

				// Also, note that we do not increment i here.
				} else {
					lps[i] = len;
					i++;
				}
			}
		}
	}

	// Function to return in-order traversal of the tree in a string.
	private static String inorder(TreeNode node) {
		if (node == null) {
			return null;
		}

		return inorder(node.left) + " " + String.valueOf(node.val) + " " + inorder(node.right);
	}

	// Function to return post-order traversal of the tree in a string.
	private static String postorder(TreeNode node) {
		if (node == null) {
			return null;
		}

		return postorder(node.left) + " " + postorder(node.right) + " " + String.valueOf(node.val);
	}

	// This function returns true if S is a subtree of T, otherwise false.
	public static boolean isSubtree(TreeNode T, TreeNode S) {

		// Base case: both trees are same.
		if (T == S) {
			return true;
		}

		// Base case: if first tree is empty but second tree is non-empty.
		if (T == null) {
			return false;
		}

		// Store in-order traversal of both trees in Tin and Sin respectively.
		String Tin = inorder(T);
		String Sin = inorder(S);

		// Return false if Sin string is not a substring of Tin string.
		if (!KMPSearch(Sin, Tin)) {
			return false;
		}

		// Store post-order traversal of both trees in Tpost and Spost respectively.
		String Tpost = postorder(T);
		String Spost = postorder(S);

		// Return false if Spost string is not a substring of Tpost string.
		if (!KMPSearch(Spost, Tpost)) {
			return false;
		}

		return true;
	}
}

C++ (g++ 5.4)

/*
    Time complexity: O(N)
    Space complexity: O(N)

    where 'N' is the number of nodes in the given binary tree 'T'.
*/

#include 

// Function to return in-order traversal of the tree in a string.
void computeLPSArray(string pat, int M, int lps[]) {

    // Length of the previous longest prefix suffix.
    int len = 0;
    int i = 1;

    // lps[0] is always 0.
    lps[0] = 0;

    // The loop calculates lps[i] for i = 1 to M-1.
    while (i < M) {

        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];

            // Also, note that we do not increment i here.
            } else {
                lps[i] = len;
                i++;
            }
        }
    }
}

bool KMPSearch(string pat, string txt) {

    int M = pat.length();
    int N = txt.length();

    // Create lps[] that will hold the longest prefix suffix values for pattern.
    int lps[M];
    int j = 0; // index for pat[].

    // Preprocess the pattern (calculate lps[] array).
    computeLPSArray(pat, M, lps);

    // Index for txt.
    int i = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M) {
            return true;
        }

        // Mismatch after j matches.
        else if (i < N && pat[j] != txt[i]) {

            // Do not match lps[0..lps[j-1]] characters, they will match anyway.
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return false;
}



string inorder(TreeNode *node)
{
    if (node == NULL)
    {
        return "NULL";
    }

    return inorder(node->left) + " " + to_string(node->val) + " " + inorder(node->right);
}

// Function to return post-order traversal of the tree in a string.
string postorder(TreeNode *node)
{
    if (node == NULL)
    {
        return "NULL";
    }

    return postorder(node->left) + " " + postorder(node->right) + " " + to_string(node->val);
}

// This function returns true if S is a subtree of T, otherwise false.
bool isSubtree(TreeNode *T, TreeNode *S)
{
    // Base case: both trees are same.
    if (T == S)
    {
        return true;
    }

    // Base case: if first tree is empty but second tree is non-empty.
    if (T == NULL)
    {
        return false;
    }

    // Store in-order traversal of both trees in Tin and Sin respectively.
    string Tin = inorder(T);
    string Sin = inorder(S);

    // Return false if Sin string is not a substring of Tin string.
    if (!KMPSearch(Sin, Tin)) {
            return false;
    }
    

    // Store post-order traversal of both trees in Tpost and Spost respectively.
    string Tpost = postorder(T);
    string Spost = postorder(S);
    
    // Return false if Spost string is not a substring of Tpost string.
    if (!KMPSearch(Spost, Tpost)) {
            return false;
        }

    return true;
}

Python (3.5)

'''
    Time complexity: O(N)
    Space complexity: O(N)

    where 'N' is the number of nodes in the given binary tree 'T'.
'''

# Function to return in-order traversal of the tree in a string.
def computeLPSArray(pat, M, lps):

    # Length of the previous longest prefix suffix.
    len = 0
    i = 1

    # lps[0] is always 0.
    lps[0] = 0

    # The loop calculates lps[i] for i = 1 to M-1.
    while (i < M):

        if (pat[i] == pat[len]):
            len += 1
            lps[i] = len
            i += 1
        else:
            if (len != 0):
                len = lps[len - 1]
            # Also, note that we do not increment i here.
            else:
                lps[i] = len
                i += 1


def KMPSearch(pat, txt):

    M = len(pat)
    N = len(txt)

    # Create lps[] that will hold the longest prefix suffix values for pattern.
    lps = [0] * M
    j = 0 # index for pat.

    # Preprocess the pattern (calculate lps[] array).
    computeLPSArray(pat, M, lps)

    # Index for txt.
    i = 0
    while (i < N):
        if (pat[j] == txt[i]):
            j += 1
            i += 1
        if (j == M):
            return True

        # Mismatch after j matches.
        elif (i < N and pat[j] != txt[i]):

            # Do not match lps[0..lps[j-1]] characters, they will match anyway.
            if (j != 0):
                j = lps[j - 1]
            else:
                i += 1

    return False



def inorder(node):

    if (node == None):
        return "NULL"

    return inorder(node.left) + " " + str(node.data) + " " + inorder(node.right)


# Function to return post-order traversal of the tree in a string.
def postorder(node):

    if (node == None):
        return "NULL"

    return postorder(node.left) + " " + postorder(node.right) + " " + str(node.data)


# This function returns true if S is a subtree of T, otherwise false.
def isSubtree(T, S):

    # Base case: both trees are same.
    if (T == S):
        return True

    # Base case: if first tree is empty but second tree is non-empty.
    if (T == None):
        return False

    # Store in-order traversal of both trees in Tin and Sin respectively.
    Tin = inorder(T)
    Sin = inorder(S)

    # Return false if Sin string is not a substring of Tin string.
    if (not KMPSearch(Sin, Tin)):
        return False
    

    # Store post-order traversal of both trees in Tpost and Spost respectively.
    Tpost = postorder(T)
    Spost = postorder(S)
    
    # Return false if Spost string is not a substring of Tpost string.
    if (not KMPSearch(Spost, Tpost)):
        return False

    return True

Given two binary trees T and S, check whether tree S has exactly the same structure and node values with a subtree of T, i.e., check if tree S is a subtree of the tree T.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

Input Format:

Explanation:

Note:

Output Format:

Note:

Constraints:

Top Snapdeal Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Snapdeal Software Developer