Space complexity of isSubtree function for 2 binary trees-CodePudding

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

    public boolean areSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (subRoot.val != root.val)
            return false;
        return areSame(root.left, subRoot.left) && areSame(root.right, subRoot.right);
    }

Is the space compelxity of my above solution to find if a tree is subtree of another binary tree - O(height(tree1)) (as suggested in most of the discussion comments) or O(height(tree1) height(tree2)) where

I think it should be O(height(tree1) height(tree2)) because isSubtree can go as deep as one branch of tree1, and for each call, the isSame() could go as deep as height(tree2), so the maximum stack memory being used at any instant would be ht1 ht2.

CodePudding user response：

Assuming that the boolean operators && and || are short-circuiting operators (as they are in Java), the recursion depth (and extra stack memory) is upper bounded by O(height(tree1)).

Since isSubtree(root, subRoot) can only call itself (with the first tree's height reduced by 1) or areSame(root, subRoot), and at most one call of 'areSame' directly from 'isSubtree' can be on the stack at a time (because of short-circuiting), the recursion depth is O(height(tree1)) max-depth-of(areSame(tree1, tree2)).

Now, areSame(root, subRoot) makes no recursive calls if root is null. If root is not null, it may call:

areSame(root.left, subRoot.left) && areSame(root.right, subRoot.right);

Here, it calls areSame only with child nodes of root: the height of the first tree has been reduced by 1, and the first call must complete before the second call starts (since && short-circuits). So there can be at most height(tree1) 1 calls to areSame on the call-stack at any time, so the total recursion depth/ stack space of isSubtree is O(height(tree1))