Problem overview
The function is_same_tree receives the roots of two binary trees, p and q, each an Option<Box<TreeNode>>, and returns true if they are the same tree. Two trees are the same when they have exactly the same shape and every node holds the same value as the node in the same place in the other tree. Two empty trees are the same. The lesson provides TreeNode, with an i32 field val and the fields left and right, both Option<Box<TreeNode>>.
The trees [1, 2, 3] and [1, 2, 3] are the same. The trees [1, 2] and [1, None, 2] hold the same values but differ in shape: the 2 is a left child in the first and a right child in the second. The trees [1, 2, 1] and [1, 1, 2] have the same shape and different values in the left child.
Approach: compare the roots, then the subtrees
Two trees are the same when their roots hold the same value, their left subtrees are the same, and their right subtrees are the same. The last two parts are the same question about smaller trees, so the function can call itself on them. The recursion stops when it reaches empty trees.
At each step there are only a few situations:
- Both trees are empty: they are the same.
- Both have a node: the values must match, and then both pairs of subtrees must be the same.
- Exactly one is empty: the shapes differ, so they are not the same.
Rust expresses this directly as a match on the pair (p, q), one arm per situation. For [1, 2] and [1, None, 2], the function compares the roots 1 and 1, then looks at the left subtrees. One is the node 2, the other is empty, so the answer is false.
The left subtrees are checked first, so the function stops at that mismatch without looking at the right ones. For [1, 2, 1] and [1, 1, 2], a run that prints each comparison shows:
compare 1 and 1
compare 2 and 1
The roots match, the left children don't, and the function returns false.
Step by step
- Match on the pair. The body is a single
match (p, q), so both trees are examined together. It has no semicolon after its closing brace, so its value is what the function returns. - Both empty. The arm
(None, None) => trueis the base case. It also ends the recursion when both trees step past a leaf at the same time. - Both present. The arm
(Some(p), Some(q))binds the two boxes, again namedpandq. Inside the arm,p.valandp.leftwork directly. - Compare the values. If
p.val != q.val,return falseat once. An early exit needsreturn, since it isn't the arm's last expression. - Compare the subtrees. The arm ends with two recursive calls, one on
p.leftandq.leftand one onp.rightandq.right, joined with&&. With no semicolon, that is the arm's value. - Everything else. The last arm,
_ => false, covers exactly one empty tree. Rust requires amatchto cover every case, and this arm completes it.
The solution in Rust
impl Solution {
fn is_same_tree(p: Option<Box<TreeNode>>, q: Option<Box<TreeNode>>) -> bool {
match (p, q) {
(None, None) => true,
(Some(p), Some(q)) => {
if p.val != q.val {
return false;
}
Self::is_same_tree(p.left, q.left) && Self::is_same_tree(p.right, q.right)
}
_ => false,
}
}
}
Rust details worth knowing:
- Matching on a tuple moves the trees.
match (p, q)builds the pair from the two arguments, which the function owns. The patterns then take the boxes out of the pair. - Arm order matters. Rust tries the arms from top to bottom. By the time
_is reached, the cases(None, None)and(Some, Some)are gone, which leaves(Some, None)and(None, Some). - Shadowing. In
(Some(p), Some(q)), the newpandqare boxed nodes, and they hide the parameters. The parameters wereOptions. - Passing subtrees by value.
p.leftis moved into the recursive call. This is fine here, because the function doesn't need the trees afterwards. Sincep.valis read before the call, andi32is copied, nothing is used after being moved. &&short-circuits. If the left pair differs, the right pair isn't compared.- The last expression. The arms are expressions of type
bool, so the wholematchis one.
Complexity
Time: O(n), where n is the number of nodes in the smaller tree. Each pair of nodes is compared at most once, and the function stops at the first difference.
Space: O(h), where h is the height of the trees, for the recursion. The lesson limits the depth to 400.
Edge cases and common mistakes
- Both trees empty.
[]and[]givetrue. - One tree empty.
[]and[0]givefalse. The_arm handles it, whichever tree is the empty one. - Same values, different shape.
[1, 2]and[1, None, 2]givefalse. Comparing the lists of values, ignoring where the missing children are, would call them equal. - A tree that extends the other.
[1, 2]and[1, 2, 3]givefalse: the second has a right child that the first doesn't. - Forgetting the value check. Comparing only the shapes gives
truefor[1, 2, 1]and[1, 1, 2]. - Treating the zero value as "missing". A node can hold 0 and is still a node:
[0]and[0]givetrue.
Testing
[1, 2, 3]and[1, 2, 3]givetrue.[1, 2]and[1, None, 2]givefalse.[1, 2, 1]and[1, 1, 2]givefalse.[]and[]givetrue.[]and[0]givefalse.[0]and[0]givetrue.[1, 2]and[1, 2, 3]givefalse.
