Checking Subtree of Another Tree using Preorder Traversal or Recursion

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

Hints:

• Which approach is better here- recursive or iterative?
• If recursive approach is better, can you write recursive function with its parameters?
• Two trees s and t are said to be identical if their root values are same and their left and right subtrees are identical. Can you write this in form of recursive formulae?
• Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)

Checking Subtree using Binary Tree Preorder Traversal

If a binary tree is the subtree of another binary tree, then its preorder traversal sequence string must be the substring of another one’s. Thus, we just need to use the recursion to obtained the binary tree preorder traversal and compare both preorder strings.

For a precise preorder traversal, we can distinguish the left and right nodes, therefore, we can pass a boolean parameter to denote whether current node is in the left or the right branch.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        string tree1 = preorder(s, true);
        string tree2 = preorder(t, true);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t, bool left) {
        if (t == nullptr) {
            if (left) {
                return "lnull";
            }
            return "rnull";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left, true) + " " +
            preorder(t->right, false);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        string tree1 = preorder(s, true);
        string tree2 = preorder(t, true);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t, bool left) {
        if (t == nullptr) {
            if (left) {
                return "lnull";
            }
            return "rnull";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left, true) + " " +
            preorder(t->right, false);
    }
};

However, this is not entirely necessary, and we can simplify the implementation a bit as the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        string tree1 = preorder(s);
        string tree2 = preorder(t);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t) {
        if (t == nullptr) {
            return "null";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left) + " " +
            preorder(t->right);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        string tree1 = preorder(s);
        string tree2 = preorder(t);
        return tree1.find(tree2) != string::npos;
    }
    
private:
    string preorder(TreeNode* t) {
        if (t == nullptr) {
            return "null";
        }
        return "#" + std::to_string(t->val) + " " +
            preorder(t->left) + " " +
            preorder(t->right);
    }
};

Time complexity : O(m^2+n^2+m*n): A total of nn nodes of the tree ss and mm nodes of tree tt are traversed. Assuming string concatenation takes O(k) time for strings of length k and indexOf takes O(m*n).

Space complexity: O(max(m,n)). The depth of the recursion tree can go upto nn for tree t and m for tree s in worst case.

Recursive Checking using Same Tree Algorithm

We can compare the nodes of the both tree. We know that if both trees are identical, then one binary tree is the sub-tree of another. To check if both trees are identical, we can recursively check the current node value and its left and right branches.

Then, if a binary tree A is subtree of another B, it must be one of these: A equals B (same tree), A’s left is subtree of B (recursive check) or A’s right is subtree of B (recursive check).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (isSame(s, t)) return true;
        if (s == nullptr) return false;
        return 
            isSubtree(s->left, t) ||
            isSubtree(s->right, t);
    }
private:
    bool isSame(TreeNode* s, TreeNode * t) {
        if (s == nullptr && t == nullptr) {
            return true;
        }
        if (s == nullptr || t == nullptr) {
            return false;
        }
        return (s->val == t->val) && 
                isSame(s->left, t->left) && 
                isSame(s->right, t->right);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (isSame(s, t)) return true;
        if (s == nullptr) return false;
        return 
            isSubtree(s->left, t) ||
            isSubtree(s->right, t);
    }
private:
    bool isSame(TreeNode* s, TreeNode * t) {
        if (s == nullptr && t == nullptr) {
            return true;
        }
        if (s == nullptr || t == nullptr) {
            return false;
        }
        return (s->val == t->val) && 
                isSame(s->left, t->left) && 
                isSame(s->right, t->right);
    }
};

Time complexity : O(m*n). In worst case(skewed tree) traverse function takes O(m*n) time.
Space complexity : O(n). The depth of the recursion tree can go upto n. n refers to the number of nodes in s.

–EOF (The Ultimate Computing & Technology Blog) —