Subtree of Another Binary Tree

NeetCode: Subtree of Another Binary Tree · LeetCode: 572. Subtree of Another Binary Tree · Difficulty: Easy

Return true if subRoot has the same structure and values as some subtree of root.

Example

Text

Input:  root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]                Output: true
Input:  root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]    Output: false

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed.

Brute force: run Same Tree at every node

Try every node of root as the match point, using the Same Tree comparison.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (isSameTree(root, subRoot)) return true;
        if (root == null) return false;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        return a.val == b.val && isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode sub = tree(4, 1, 2);
        System.out.println(new Solution().isSubtree(tree(3, 4, 5, 1, 2), sub));
        System.out.println(new Solution().isSubtree(tree(3, 4, 5, 1, 2, null, null, null, null, 0), sub));
    }
}

Output

true
false

Time: O(m · n) for trees with m and n nodes. Space: O(h).

Alternative: serialize both and search for the substring

Serialize each tree in preorder with N for missing children. A subtree is exactly a contiguous piece of that listing. Writing every token with a leading comma, plus a final comma, makes sure a match starts and ends on token boundaries (so ,2, cannot match inside ,12,). String.contains does the search.

Building the two strings takes O(m + n). Java's String.contains does not promise linear time: a straightforward implementation compares from every start position, so the search step is O(m · n) in the worst case. A search with a linear guarantee (KMP or the Z-function) makes the whole solution O(m + n). These algorithms are not covered here.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return serialize(root).contains(serialize(subRoot));
    }

    String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        sb.append(',');
        return sb.toString();
    }

    private void write(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(",N");
            return;
        }
        sb.append(',').append(node.val);
        write(node.left, sb);
        write(node.right, sb);
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode sub = tree(4, 1, 2);
        System.out.println(solution.serialize(sub));
        System.out.println(solution.isSubtree(tree(3, 4, 5, 1, 2), sub));
        System.out.println(solution.isSubtree(tree(3, 4, 5, 1, 2, null, null, null, null, 0), sub));
        System.out.println(solution.isSubtree(tree(12), tree(2)));
    }
}

Output

,4,1,N,N,2,N,N,
true
false
false

Time: O(m + n) to build the strings, plus the substring search (O(m · n) worst case with String.contains). Space: O(m + n) for the strings. The last line checks the token boundaries: a tree with root 2 must not match inside a tree with root 12.