Same tree and subtree checks

Why this matters

Two questions come up again and again with trees. Are these two trees exactly the same? Does a smaller tree appear somewhere inside a bigger one? A file system gives you both questions. Two folders are copies of each other only if they hold the same files in the same folders. A backup tool may want to find every place where a known folder layout appears inside a larger drive.

Both questions use one tool: recursion, which means a function that calls itself on smaller pieces of its input. The function looks at one node, then asks the same question about the left child and the right child. This lesson builds the two checks step by step. It assumes you know what a node, a root, a left child and a right child are. If not, read the terminology lesson first.

The previous lessons in this module walk trees with traversals and build trees from lists. This lesson uses a different question: not "what are the values", but "do these two trees have the same shape and values".

The idea: same means same at every node

Start with two small trees drawn as text.

Tree a:        Tree b:
    1              1
   / \            / \
  2   3          2   3

Are they the same? Yes. The root holds 1 in both. The left child holds 2 in both. The right child holds 3 in both. Neither child has a child of its own. Every position matches.

Now look at tree c:

Tree c:
    1
     \
      2

Tree c has the same values as tree a, except for 3. Its 2 is on the right side, not the left. It is not the same tree. The values alone do not decide the question. The position of each value matters too.

From this example you can write the rule in plain words. Two trees are the same when:

1. Both are empty, or
2. Both are not empty, and their roots hold the same value, and their left subtrees are the same, and their right subtrees are the same.

The second rule uses the word subtree. A subtree is one node together with all the nodes below it. The left subtree of a node is the tree that starts at its left child. The rule says "compare the left subtrees" and "compare the right subtrees", which is the same question on smaller trees. That is what makes it recursion.

The first rule is the stopping point, which programmers call the base case. An empty tree has no nodes at all. In C++ an empty tree is the null pointer, written nullptr. Without this rule the recursion would keep going past the leaves into empty children, which have no value to read.

Setting up the nodes in C++

Each node stores one int and two pointers to its children. The course uses std::unique_ptr for those pointers. A std::unique_ptr is a smart pointer: it owns the node it points to and deletes that node automatically when it goes out of scope. You do not need to call delete yourself.

#include <iostream>
#include <memory>
#include <utility>
#include <vector>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};
 
std::unique_ptr<Node> make(int value,
                           std::unique_ptr<Node> left = nullptr,
                           std::unique_ptr<Node> right = nullptr) {
    auto node = std::make_unique<Node>();
    node->value = value;
    node->left = std::move(left);
    node->right = std::move(right);
    return node;
}

The helper make builds one node and attaches the children you pass in. Nested calls build a whole tree in one expression. This line builds tree a from the picture above:

auto a = make(1, make(2), make(3));

The comparison functions do not need to own the tree, so they take a plain pointer, written const Node*. The const means the function promises not to change the nodes. To get a plain pointer from a std::unique_ptr, call .get(). So a.get() is the address of the root node of a. The left child of a node is node->left.get().

Writing same_tree

Here is the comparison. Read it slowly, one case at a time.

bool same_tree(const Node* a, const Node* b) {
    if (a == nullptr || b == nullptr) {
        return a == b;
    }
    return a->value == b->value
        && same_tree(a->left.get(), b->left.get())
        && same_tree(a->right.get(), b->right.get());
}

The first if handles the case where at least one side is empty. The return statement a == b is true only when both pointers are null. Think of the four possibilities:

When both are non-empty, the return line compares three things with &&. The && operator means "and", and C++ stops at the first false part. So the function checks the values first, then the left subtrees, then the right subtrees. If the values differ, the recursive calls never run.

Trace tree a against tree c from the earlier picture. Let the first tree be a, and let the second be c, which is make(1, nullptr, make(2)).

1. Both roots are non-null. Values are 1 and 1, so they match. Check the left subtrees.
2. Left of a is node 2. Left of c is empty. One is empty and the other is not, so the call returns false.
3. The && chain stops. same_tree returns false.

Notice that the function never checked the right children in this trace. It did not need to. One mismatch is enough to answer "not the same".

Example 1: same shape, different objects

The first program builds several trees and compares them. It shows that the function looks at shape, not at the order the nodes were created in.

int main() {
    std::cout << std::boolalpha;
 
    auto a = make(1, make(2), make(3));
    auto b = make(1, make(2), make(3));
    auto c = make(1, nullptr, make(2));
    auto d = make(1, make(2));
 
    std::cout << "a vs b: " << same_tree(a.get(), b.get()) << '\n';
    std::cout << "a vs c: " << same_tree(a.get(), c.get()) << '\n';
    std::cout << "c vs d: " << same_tree(c.get(), d.get()) << '\n';
    std::cout << "a vs nullptr: " << same_tree(a.get(), nullptr) << '\n';
    std::cout << "nullptr vs nullptr: " << same_tree(nullptr, nullptr) << '\n';
    return 0;
}

The std::boolalpha line makes true and false print as words instead of 1 and 0. Here is the output from running the program with g++ 15 and -std=c++20 -Wall:

a vs b: true
a vs c: false
c vs d: false
a vs nullptr: false
nullptr vs nullptr: true

Tree a and tree b are different objects in memory, yet they match. The function compares content, not addresses. Tree c and tree d both have one child, but in different places, so they do not match. The last line shows the base case in action: two empty trees are the same.

Pause on the last two lines of output. They are the two base cases from the first rule. Any correct version of same_tree must return true for two empty trees and false for an empty tree against a non-empty one.

Subtree checks: does one tree appear inside another?

Now the second question. A tree sub is a subtree of a tree root when some node inside root has a subtree that is exactly the same as sub. In other words, cut out any node of root together with everything below it, and see whether the cut-out piece matches sub.

The check needs to try every node of root, because the match can start at any position. The idea fits in one sentence: ask same_tree at the root, then at the root's left child, then at the root's right child, and so on, until a match is found or the tree runs out.

bool is_subtree(const Node* root, const Node* sub) {
    if (sub == nullptr) {
        return true;
    }
    if (root == nullptr) {
        return false;
    }
    return same_tree(root, sub)
        || is_subtree(root->left.get(), sub)
        || is_subtree(root->right.get(), sub);
}

Read the two if lines first. The empty tree sub is treated as a subtree of every tree. That is a convention: nothing is missing from the bigger tree. The second if says that a non-empty sub cannot be found inside an empty root.

The return line uses ||, which means "or". C++ stops at the first true part. So as soon as same_tree(root, sub) finds a match at the current node, the search stops. If not, it moves on to the left subtree of root, and only if that fails, to the right subtree.

Example 2: finding a subtree

The next program builds a larger tree, then checks five smaller trees against it.

          10
         /  \
        4    7
       / \    \
      1   6    9
               /
              8

int main() {
    std::cout << std::boolalpha;
 
    auto big = make(10,
                    make(4, make(1), make(6)),
                    make(7, nullptr, make(9, make(8))));
 
    auto sub1 = make(4, make(1), make(6));
    auto sub2 = make(4, make(1));
    auto sub3 = make(9, make(8));
    auto sub4 = make(7, nullptr, make(9));
    auto sub5 = make(9, nullptr, make(8));
 
    std::cout << "sub1 (4 with 1 and 6): " << is_subtree(big.get(), sub1.get()) << '\n';
    std::cout << "sub2 (4 with only 1): " << is_subtree(big.get(), sub2.get()) << '\n';
    std::cout << "sub3 (9 with left 8): " << is_subtree(big.get(), sub3.get()) << '\n';
    std::cout << "sub4 (7 with right 9): " << is_subtree(big.get(), sub4.get()) << '\n';
    std::cout << "sub5 (9 with right 8): " << is_subtree(big.get(), sub5.get()) << '\n';
    std::cout << "empty tree: " << is_subtree(big.get(), nullptr) << '\n';
    std::cout << "sub1 in an empty tree: " << is_subtree(nullptr, sub1.get()) << '\n';
    return 0;
}

Output:

sub1 (4 with 1 and 6): true
sub2 (4 with only 1): false
sub3 (9 with left 8): true
sub4 (7 with right 9): false
sub5 (9 with right 8): false
empty tree: true
sub1 in an empty tree: false

Each line teaches something. sub1 is the whole left subtree of the root, so it matches at the node 4. sub2 has the value 4 at the top, just like sub1, but its right child is missing. same_tree sees a child on one side and an empty pointer on the other, and says no. sub3 matches the subtree that starts at 9. sub4 is the near miss: the value 7 is in the right place, and so is 9, but 9 in the big tree has a left child 8 that sub4 lacks. sub5 has the right shape but the wrong side for 8, so it does not match either.

To see the search at work, consider sub3 in detail. The search starts at 10. same_tree(10, 9-with-8) fails because the values differ. Then is_subtree calls itself on the left child, 4. That subtree has no 9, so the search fails there, and it fails at 1 and 6 as well. Then it moves to the right child, 7. At 7, same_tree fails again, because 7 is not 9. The search moves to 7's left child, which is empty, and returns false for it. Then it moves to 7's right child, 9. Now same_tree(9, 9-with-8) compares the values, both 9, then the left children, 8 and 8, which match, then the right children, both empty, which match. The answer is true.

Example 3: why the search has to try every node

Consider a case where the same value appears in many places. Suppose root is a chain of nodes all holding 1, and sub holds 1 with a single child 1. The search tests each node of root. At the top, same_tree may succeed. But if the match is at the bottom of the chain, the search has to walk down to it and compare at each node on the way.

The cost is worth knowing. Let n be the number of nodes in root and m the number of nodes in sub. Each call to same_tree can take up to m steps, because it stops when it reaches the bottom of sub. The search calls same_tree at up to n nodes. So the worst case is about n times m steps. Written with the usual notation, that is O(n × m). The notation O is the standard way to describe how the work grows as the input grows, and the lesson on time and space complexity explains it in detail.

For a course exercise, the O(n × m) cost is fine. For very large trees a faster method exists, such as turning each tree into a string and searching that string. The serialization lesson in this module covers that idea.

Common mistakes

These mistakes come up in most first attempts. Each one shows the wrong code, what it prints, and what goes wrong.

Mistake 1: comparing lists of values

A tempting shortcut is to write both trees out as lists and compare the lists. An in-order list visits the left subtree, then the node, then the right subtree. Two different trees can give the same list.

void inorder(const Node* n, std::vector<int>& out) {
    if (n == nullptr) return;
    inorder(n->left.get(), out);
    out.push_back(n->value);
    inorder(n->right.get(), out);
}
 
// x is 2 with left child 1, y is 1 with right child 2
auto x = make(2, make(1));
auto y = make(1, nullptr, make(2));
std::vector<int> vx, vy;
inorder(x.get(), vx);
inorder(y.get(), vy);
std::cout << std::boolalpha << "same list: " << (vx == vy) << '\n';

Output:

same list: true

Both lists are 1 2, but the trees are different. The shapes are not the same. Compare the trees node by node, as same_tree does.

Mistake 2: comparing child pointers with ==

With std::unique_ptr, a tempting line is a->left == b->left. This compares the addresses of the two child nodes, not their contents. Two children with the same value and shape live at different addresses, so the answer is false.

auto a = std::make_unique<Node>();
auto b = std::make_unique<Node>();
a->value = 5;
b->value = 5;
a->left = std::make_unique<Node>();
b->left = std::make_unique<Node>();
a->left->value = 3;
b->left->value = 3;
std::cout << std::boolalpha;
std::cout << "values equal: " << (a->value == b->value) << '\n';
std::cout << "left child values equal: " << (a->left->value == b->left->value) << '\n';
std::cout << "left children pointers equal: " << (a->left == b->left) << '\n';

Output:

values equal: true
left child values equal: true
left children pointers equal: false

The last line is false even though the two left children hold the same value. Always compare ->value and recurse into the children. Never compare the children themselves with ==.

Mistake 3: passing a unique_ptr by value

A beginner may write same_tree(std::unique_ptr<Node> a, std::unique_ptr<Node> b). A std::unique_ptr cannot be copied, so passing it by value tries to copy it, and the compiler stops. The output below is the first lines of the g++ 15 error, trimmed:

bad_byvalue.cpp: In function 'int main()':
bad_byvalue.cpp:19:21: error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]'
   19 |     return same_tree(x->left, y->left) ? 0 : 1;

The fix is the signature used in this lesson, with const Node* parameters and .get() at each call. A function that only looks at a tree should not own it.

Mistake 4: forgetting the null check

If a function dereferences a child without checking it first, it crashes when that child is empty. Dereferencing means reading through a pointer with ->. Here is a version with no null checks:

bool same_tree_no_check(const Node* a, const Node* b) {
    return a->value == b->value
        && same_tree_no_check(a->left.get(), b->left.get())
        && same_tree_no_check(a->right.get(), b->right.get());
}

Called on two single nodes, it reads a->left.get(), which is null, and then tries a->value on that null pointer. The program is stopped by the operating system. When the program was run from a shell, it ended with exit code 139, which means it was killed by a segmentation fault. A segmentation fault is an error that happens when a program reads memory it is not allowed to read. Always check for nullptr before using ->.

Mistake 5: checking only the root

A subtree check that only calls same_tree on the root is wrong, because the match can start lower down. Here is that version, called on sub3 from Example 2:

bool is_subtree_root_only(const Node* root, const Node* sub) {
    return same_tree(root, sub);
}

Output:

sub3 with root-only check: false

The answer should be true, since sub3 is the subtree at 9. The root is 10, so the root-only version compares 10 with 9 and gives up. The search has to visit every node, as is_subtree does.

Practice

Each exercise is followed by its answer. Try it on paper or in a file before you read the answer.

Exercise 1: predict the result

Given auto x = make(1, make(2)); and auto y = make(1, nullptr, make(2));, what does same_tree(x.get(), y.get()) return?

Show the answer

It returns false. Both trees have the values 1 and 2, but in x the 2 is the left child and in y the 2 is the right child. At the root, the values match. Then the left children are compared: x has a node, y has none, so the call returns false.

Exercise 2: find the bug

This version is meant to return true when one side is empty. Why is it wrong?

bool same_tree_buggy(const Node* a, const Node* b) {
    if (a == nullptr || b == nullptr) {
        return true;
    }
    return a->value == b->value
        && same_tree_buggy(a->left.get(), b->left.get())
        && same_tree_buggy(a->right.get(), b->right.get());
}

Show the answer

The first if returns true whenever one side is empty, even if the other side has a node. Then a single node 1 and a node 1 with a left child 2 compare as equal. The program prints true for them, but they are different trees. The fix is return a == b;, which is true only when both are empty. Run same_tree_buggy and same_tree on the same pair to see the difference: the buggy version prints true, the fixed version prints false.

Exercise 3: count the copies

Write int count_copies(const Node* root, const Node* sub) that returns how many nodes of root have a subtree equal to sub. For root equal to make(1, make(2), make(2)) and sub equal to make(2), the answer is 2.

Show the answer

int count_copies(const Node* root, const Node* sub) {
    if (root == nullptr) {
        return 0;
    }
    int here = same_tree(root, sub) ? 1 : 0;
    return here + count_copies(root->left.get(), sub)
                + count_copies(root->right.get(), sub);
}

The function checks the current node, then adds the counts from the left and right subtrees. It was run on the example above and printed 2. A second run, with root set to make(1, make(2, make(3)), make(2, make(3))) and sub set to make(2, make(3)), printed 2 as well.

Exercise 4: work out the cost

A chain of 100 nodes holding 1 is searched for a chain of 10 nodes holding 1. Roughly how many node comparisons can happen in the worst case?

Show the answer

About 1,000. The search calls same_tree at up to 100 nodes. Each call can compare up to 10 nodes before it finds the bottom of sub. So the worst case is about 100 times 10, which is 1,000 comparisons. The number is a rough upper bound, since the first few comparisons at each node can stop early.

Exercise 5: why the empty case is true

Why does is_subtree(big, nullptr) return true, and why would returning false be a worse choice?

Show the answer

An empty tree has no nodes that could be missing, so the function says it is always found. Returning false would say "not found" for something that has nothing to find. Either choice works if the code states it. The is_subtree in this lesson returns true.

Putting it together

The full program in one block, ready to compile with g++ -std=c++20 -Wall:

#include <iostream>
#include <memory>
#include <utility>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};
 
std::unique_ptr<Node> make(int value,
                           std::unique_ptr<Node> left = nullptr,
                           std::unique_ptr<Node> right = nullptr) {
    auto node = std::make_unique<Node>();
    node->value = value;
    node->left = std::move(left);
    node->right = std::move(right);
    return node;
}
 
bool same_tree(const Node* a, const Node* b) {
    if (a == nullptr || b == nullptr) {
        return a == b;
    }
    return a->value == b->value
        && same_tree(a->left.get(), b->left.get())
        && same_tree(a->right.get(), b->right.get());
}
 
bool is_subtree(const Node* root, const Node* sub) {
    if (sub == nullptr) {
        return true;
    }
    if (root == nullptr) {
        return false;
    }
    return same_tree(root, sub)
        || is_subtree(root->left.get(), sub)
        || is_subtree(root->right.get(), sub);
}
 
int main() {
    std::cout << std::boolalpha;
 
    auto a = make(1, make(2), make(3));
    auto b = make(1, make(2), make(3));
    auto c = make(1, nullptr, make(2));
 
    std::cout << "a vs b: " << same_tree(a.get(), b.get()) << '\n';
    std::cout << "a vs c: " << same_tree(a.get(), c.get()) << '\n';
 
    auto big = make(10,
                    make(4, make(1), make(6)),
                    make(7, nullptr, make(9, make(8))));
    auto sub = make(9, make(8));
 
    std::cout << "sub in big: " << is_subtree(big.get(), sub.get()) << '\n';
    return 0;
}

Output:

a vs b: true
a vs c: false
sub in big: true

Summary

• Two trees are the same when both are empty, or when their values match and their left and right subtrees are the same.
• The base case is the empty tree. Check for nullptr before using ->.
• Compare trees node by node. Comparing lists of values can call different trees the same.
• A subtree check runs same_tree at every node of the bigger tree, since the match can start anywhere.
• The subtree check costs about n times m steps in the worst case, where n and m are the sizes of the two trees.