Leetcode: Subtree of Another Tree

Question

My solution to the LeetCode's Subtree of Another Tree passes all the test cases, but the code feels and looks ugly. Would appreciate an advice on how to improve it.

The problem:

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example:

Given tree s:

 3 / \ 4 5 / \ 1 2 

Given tree t:

 4 / \ 1 2 

Return true, because t has the same structure and node values with a subtree of s.

My solution:

class Solution { private: bool isSame(TreeNode* root_s, TreeNode* t) { if (!root_s && !t) return true; if (root_s && !t) return false; if (!root_s && t) return false; if (root_s->val != t->val) return false; return isSame(root_s->left, t->left) && isSame(root_s->right, t->right); } void preorder (TreeNode* s, TreeNode* t, bool& is_subtree) { if (!s) return; if (s->val == t->val) { if (isSame(t,s)) { is_subtree = true; return; } } preorder (s->left, t, is_subtree); preorder (s->right, t, is_subtree); } public: bool isSubtree(TreeNode* s, TreeNode* t) { bool is_subtree = false; preorder (s, t, is_subtree); return is_subtree; } }; 

For context, here's the definition of TreeNode given by LeetCode:

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; 

Answer 1

Your code doesn't look that ugly! Here are some suggestions to make it better. Note that LeetCode makes significantly more mistakes than you when it comes to code quality; I have listed the suggestions for LeetCode-provided stuff too, so that you don't make the same mistakes when you are writing real code — you don't have to force LeetCode to accept them (i.e., some of them can be compromised for the purpose of passing their tests).

General design

The Solution class is very Java-style AFAIK, but it is not idiomatic in C++. It should be replaced by a namespace, or removed altogether. In C++, it is preferred to create a separate Tree class for the binary trees, instead of operating directly on the nodes. Also, the value type should be a template parameter for reusability.

Naming

In C++, functions and variables are generally named in snake_case, with CamelCase names reserved for classes.

The name of the function is misleading — to me, isSubtree(s, t) means "s is a subtree of t," rather than the reverse. contains_subtree may be better. The parameters s and t are also non-descriptive and thus unreadable; I recommend tree and subtree.

The parameters to isSame (or maybe just same), on the other hand, can be named as simply as tree_a and tree_b, because the semantics is unambiguous.

Logic

(Note: the code snippets presented are intended to help you understand the review. They are not tested; in other words, they and may contain mistakes and are not guaranteed to work.)

The logic of same can be simplified:

• if both arguments are non-null, then they are identical if and only if

  • their values are equal; and

  • their left subtrees are identical; and

  • their right subtrees are identical;

• otherwise, they are identical if and only if they are both null.

bool same(TreeNode* tree_a, TreeNode* tree_b) { if (tree_a && tree_b) { return tree_a->val == tree_b->val && same(tree_a->left, tree_b->left) && same(tree_a->right, tree_b->right); } else { return !tree_a && !tree_b; } } 

This presents your logic in a way that is (hopefully) more readable.

Similarly,

• if tree is non-null, then tree contains subtree if and only if

  • same(tree, subtree); or

  • tree->left contains subtree; or

  • tree->right contains subtree;

• otherwise, tree contains subtree if and only if subtree is null as well.

bool contains_subtree(TreeNode* tree, TreeNode* subtree) { if (tree) { return same(tree, subtree) || contains_subtree(tree->left, subtree) || contains_subtree(tree->right, subtree); } else { return !subtree; } } 

This refactoring eliminates the unnatural non-local control flow (i.e., writing to the bool& argument instead of using the return value). It also ensures that the function returns as soon as a match is found.