Home > Reflections | ⏮️ ⏭️

2024-07-05

🏋 Coding Practice

Yesterday, I failed to implement a working solution for this LeetCode problem.
It’s time for round 2.

101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

🪞 Reflections

1. 🎉 Success!
2. Previously, I’d tried to avoid reflection & equality checking because it seemed kinda wasteful and clunky. That was a mistake. Whatever seems most obviously correct should probably be the first choice to implement during an interview.
3. < 16 minutes is pretty good.
4. Manual testing is tedious sometimes, and annotating tree state for recursive functions is even more tedious and can be error prone.

⌨️ My Solution

/* Plan:  
1. reflect the tree  
2. check if the tree is equal to its reflection  
runtime complexity: O(N)  
extra space complexity: O(N)  
[0:36] Done planning  
[6:37] Done with initial implementation  
[12:54] finished manual test of recursive reflection function  
thought I found a bug, but then realized I'd actually just misinterpreted my own tree annotation  
[15:16] partially tested equal function  
no bugs found  
[15:47] successful submission  
*/  
/**  
 * Definition for a binary tree node.  
 * class TreeNode {  
 *     val: number  
 *     left: TreeNode | null  
 *     right: TreeNode | null  
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {  
 *         this.val = (val===undefined ? 0 : val)  
 *         this.left = (left===undefined ? null : left)  
 *         this.right = (right===undefined ? null : right)  
 *     }  
 * }  
 */  
function reflect(root: TreeNode | null): TreeNode | null { // [2,4,3]; [4]; [3]; [2,3,4]; [1,2,2,3,4,4,3]  
  if (!root || (!root.left && !root.right)) return root  
  return new TreeNode(root.val, reflect(root.right), reflect(root.left)) // [1,2,2,3,4,4,3]; [2,3,4]; [2,4,3]; [4]; [3]  
}  
  
function equal(tree1: TreeNode | null, tree2: TreeNode | null): boolean { // null null; [3] [3]; [2,3,4] [2,3,4]; [1,2,2,3,4,4,3] [1,2,2,3,4,4,3]  
  if (!tree1 && !tree2) return true // T  
  if (!tree1 || !tree2) return false  
  if (tree1.val !== tree2.val) return false  
  return equal(tree1.left, tree2.left) && equal(tree1.right, tree2.right)  
}  
  
function isSymmetric(root: TreeNode | null): boolean { // [1,2,3,4,2,3,4]  
  const reflection: TreeNode | null = reflect(root)  
  return equal(root, reflection)  
};