Check if subtree

Intuition

Two binary trees are identical if and only if their inorder traversals — with explicit null markers — match. So checking whether T2 is a subtree of T1 reduces to checking whether T2's inorder serialization appears as a contiguous subsequence inside T1's. That subsequence search is solved in linear time with KMP, turning an O(m×n) brute-force comparison into O(m+n).

Algorithm

1Run inorder(root1, list1): for each null child insert 0 as a sentinel.
2Run inorder(root2, list2): same null-marker convention.
3Build the KMP LPS (Longest Proper Prefix-Suffix) array for list2.
4KMP-scan list1 with list2 as the pattern; if index j reaches list2.size(), a full match was found.
5Return true on match, false if the scan exhausts list1.

Example Walkthrough

Input: root1 = [1, 2, 3], root2 = [2]

1.Inorder(root1): [0, 2, 0, 1, 0, 3, 0] (0 = null marker).
2.Inorder(root2): [0, 2, 0].
3.LPS for [0, 2, 0] = [0, 0, 1].
4.KMP scan: list1[0..2] = [0,2,0] matches list2 fully at j=3.
5.Match found — root2 is a subtree of root1.

Output: true

Common Pitfalls

•Omitting null markers makes structurally different trees look identical — e.g., a left-only child and a right-only child with the same value produce the same inorder list without markers.
•Using 0 as a null sentinel collides with node values that are actually 0; a safer sentinel is a value outside the problem's allowed node-value range.
•An empty T2 (root2 == null) is always a subtree; the inorder list for null is just [0], and [0] appears in every non-empty tree's serialization.

Check if subtree.java

Java


import java.util.*;

class Node {

    int data;
    Node left;
    Node right;

    Node(int x) {
        data = x;
        left = right = null;
    }
}

// Approach: Serialize both trees via inorder traversal (inserting 0 as a null-node marker),
// then use KMP substring search to check whether root2's inorder sequence appears inside root1's.
// Null markers are essential — without them, different tree shapes can produce identical inorder lists.
// Time: O(m + n) Space: O(m + n)

class Solution {

    public boolean isSubTree(Node root1, Node root2) {
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();

        inorder(root1, list1);
        inorder(root2, list2);

        return isSublist(list1, list2);
    }

    public boolean isSublist(ArrayList<Integer> list, ArrayList<Integer> sublist) {
        if (sublist.isEmpty()) {
            return true;
        }
        if (sublist.size() > list.size()) {
            return false;
        }

        // Compute LPS array for the sublist
        int[] lps = computeLPS(sublist);

        int i = 0; // index for list
        int j = 0; // index for sublist

        while (i < list.size()) {
            if (list.get(i).equals(sublist.get(j))) {
                i++;
                j++;
            }

            if (j == sublist.size()) {
                return true; // Found complete match
            } else if (i < list.size() && !list.get(i).equals(sublist.get(j))) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return false;
    }

    private int[] computeLPS(ArrayList<Integer> pattern) {
        int[] lps = new int[pattern.size()];
        int len = 0;
        int i = 1;

        while (i < pattern.size()) {
            if (pattern.get(i).equals(pattern.get(len))) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }

    public void inorder(Node root, ArrayList<Integer> list) {
        if (root == null) {
            list.add(0);
            return;
        }
        inorder(root.left, list);
        list.add(root.data);
        inorder(root.right, list);
    }
}

Was this solution helpful?