Three proposed strategies for Symmetric Tree:
isSameTree(root.left, root.right).Click below to open!
Nope — only one of the three is right! Both 1 and 2 fail, and interestingly they fail on different trees, so no single counterexample catches both. Read the breakdown below.
Strategy 1 feels so good! But it’s wrong. Here’s a tree that shows it is incorrect:
1
/ \
3 2
/ /
2 3
The in-order traversal reads 2, 3, 1, 3, 2 — a perfect palindrome! But the
tree isn’t symmetric! The 3 vs 2 positioning is clearly different in the left
and right subtrees.
Not correct! Here’s a tree that breaks it:
1
/ \
2 2
\ /
3 3
That tree is symmetric — fold it down the middle and it matches. But
isSameTree(root.left, root.right) compares left.left (null) against
right.left (3), says “these differ,” and returns false.
The bug is that equality isn’t mirroring. isSameTree pairs left with left
and right with right. Symmetry pairs left with right:
isMirror(a, b) = a.val == b.val
&& isMirror(a.left, b.right)
&& isMirror(a.right, b.left)
That’s an actual answer to this problem.
✅ That’s right. Build a mirrored copy, compare it to the original, done.
It does have the downside that it allocates a whole second tree to answer a yes/no question! The better efficient solution is in the dropdown for #2.
Only one of the three actually works. Strategies 1 and 2 both fail, on two different trees. Click on the other answers to see the explanations for why!
There is one of the three that actually works! Strategies 1 and 2 both fail, on two different trees, but the third works. Click on the other answers to see the explanations for why!
This is a very representative data structures problem – it requires thinking about tree shapes, what “correct” means, and what potential examples could break your implementation. It does this without thinking about specific code, but about solution shapes. This is the kind of thinking an engineer does before picking an approach to a problem, and also is the kind of language you could use to talk to colleagues (or an agent!) about code at a high level.
Here are some implementations of symmetric tree (not directly from students, representative of what we saw in the quiz question and in what folks sent to me)
The direct version in C, the trick is the swap in the recursive calls:
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
static bool isMirror(struct TreeNode *a, struct TreeNode *b) {
if (a == NULL && b == NULL) return true;
if (a == NULL || b == NULL) return false;
return a->val == b->val
&& isMirror(a->left, b->right) /* left against right */
&& isMirror(a->right, b->left); /* and right against left */
}
bool isSymmetric(struct TreeNode *root) {
return root == NULL || isMirror(root->left, root->right);
}
And strategy 3 — build the reflection as a brand-new tree, then ask whether it’s the same as the original — in Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mirrored(node):
if node is None: return None
# the swap happens here, at construction time
return TreeNode(node.val, mirrored(node.right), mirrored(node.left))
def same_tree(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
return (a.val == b.val
and same_tree(a.left, b.left)
and same_tree(a.right, b.right))
def isSymmetric(root):
return same_tree(root, mirrored(root))
Both are correct. The first version swaps as it compares, so it returns
false the first time it finds a mismatch; it never allocates anything. The
second version swaps as it builds, so it constructs an entire second tree
before it starts checking. Same idea, and one of them does a lot more work to
get there. (This isn’t a language comparison – you could implement the
mirroring one in C and the checking one in Python, I just like showing lots of
examples).
Also from previous weeks: If you’re not sure about the lastword.c and
tree.c bugs, we had some discussion and posts about both on Discord – you can
just sign in and scroll around to see those.
This video works through the key properties of binary search trees, and a mistake that’s easy to make when checking one:
Then try Recover Binary Search Tree, which steps up from checking a BST to repairing one — exactly two nodes have been swapped, and you have to find them:
https://leetcode.com/problems/recover-binary-search-tree/description/
Send it in if you want to; this one is more of a challenge than past weeks!
Never too late to start, no deadline, no pressure — a month from now is fine.
Joe
The code from the video is copied here for your reference:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null) { return true; }
else {
boolean leftIsBST = isValidBST(root.left);
boolean rightIsBST = isValidBST(root.right);
boolean leftAllSmaller = allSmaller(root.left, root.val);
boolean rightAllLarger = allLarger(root.right, root.val);
return leftIsBST && rightIsBST && leftAllSmaller && rightAllLarger;
}
}
public boolean allLarger(TreeNode node, int val) {
if(node == null) { return true; }
else {
if(node.val <= val) { return false; }
return allLarger(node.left, val) && allLarger(node.right, val);
}
}
public boolean allSmaller(TreeNode node, int val) {
if(node == null) { return true; }
else {
if(node.val >= val) { return false; }
return allSmaller(node.left, val) && allSmaller(node.right, val);
}
}
}