CODEWITHSUNDEEP
algorithmbinary-treesubtree
Fihop
Fihop

Reputation: 3177

"cracking the coding interview(fourth edition)": 4.7 subtree checking

You have two very large trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1

The author gives a brute force search solution, just do comparison one node by one node. The following is the code:

boolean containsTree(TreeNode t1, TreeNode t2) {
    if (t2 == null) return true;
    else return subTree(t1, t2);
}

boolean subTree(TreeNode r1, TreeNode r2) {
    if(r1 == null)
        return false;
    if(r1.data = r2.data){
        if(matchTreee(r1, r2)) return true;
    }
    return ( subTree(r1.left, r2) || subTree(r1.right, r2) );
}

boolean matchTree(TreeNode r1, TreeNode r2){
    if (r2 == null && r1 == null)
        return true;
    if (r1 == null || r2 == null)
        return false; //big tree empty & subtree still not found
    if (r1.data != r2.data)
        return false;
    return (matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right));
}

In the above code, I don't agree with the base cases for the function matchTree

if (r2 == null && r1 == null)
    return true;
if (r1 == null || r2 == null)
    return false; // big tree empty & subtree still not found

According to my understanding, the base cases should be:

    if(r2 == null) return true; //if r2 is null, r2 must match r1 
no matter r1 is null or not
    if(r1 == null) return false; //r1 == null means big tree empty 
and we already know r2 != null, so r2 must not match r1.

Can you guys help me verify it?

Thanks,

Upvotes: 0

Views: 873

Answers (1)

vlad
vlad

Reputation: 4778

It looks to me like the author of the book had a different definition in mind for T2 is a subtree of T1 than you do.

For example, consider the trees below (mad Paint skills):

Trees

The author's code considers T3 to be a subtree of T1, but not T2. Yours considers both T2 and T3 to be subtrees of T1.

That said, I think your base cases make more sense for a 'natural' definition of 'subtree'.

C# test code (with data of type int):

var t1 = new TreeNode() { data = 0,
    left = new TreeNode() { data = 1,
        left = new TreeNode() { data = 2 },
        right = new TreeNode() { data = 3, 
            right = new TreeNode() { data = 4 } } } };

var t2 = new TreeNode() { data = 1,
    left = new TreeNode() { data = 2 },
    right = new TreeNode() { data = 3 } };

var t3 = new TreeNode() { data = 1,
    left = new TreeNode() { data = 2 },
    right = new TreeNode() { data = 3,
        right = new TreeNode() { data = 4 } } };

Upvotes: 1

Related Questions