Home > Reflections | ⏮️ ⏭️

2024-07-04

🏋 Coding Practice

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. This seems hard for an easy problem. Maybe I’m overlooking something…
2. To be continued…

⌨️ My Solution

/* determine if a tree is symmatrical  
Thoughts:  
seems hard to recursively check for symmetry, since symmetry is judged from the root  
Plan:  
1. convert tree to levels  
2. check if levels are symmetric  
runtime complexity: O(N)  
extra space complexity: O(N)  
[4:13] Done planning  
[10:00] Done with initial implementation  
[15:15] Done with test  
Bugs found after manual testing:  
1. duplicate named function (isSymmetric)  
2. didn't set default value for levels in treeToLevels helper  
3. wrong answer: [1,2,2,null,3,null,3] -> true (expected false)  
- I need to insert nulls into my levels to track their posiiton  
- how do I do this without infinite looping with nulls?  
- Easiest way seems to be checking the depth first  
[27:18] Done adding depth check and adjusting code  
next bugs found:  
- missing else clause in ternaries in new depth function  
- null pointer dereferencing in treeToLevels  
- wrong answer: [1, 0] -> true (expected false)  
  - (falsey) zeros defaulted to null; add type check  
[32:10] time limit exceeded  
🤔 seems like filling out the entire tree takes too long  
... we probably have degenerate skinny trees, so we're filling out exponentially more nodes than were provided  
... we need a way to determine symmetry without having to build out the entire tree, filling in nodes  
... but not right now. I thought this would be quick and now it's dinner time.  
[43:26] To be continued...  
*/  
/**  
 * 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 depth(root: TreeNode | null, max = 0): number {  
  if (!root) return max  
  const leftDepth: number = depth(root.left, max + 1)  
  const rightDepth: number = depth(root.right, max + 1)  
  return Math.max(leftDepth, rightDepth)  
}  
  
function treeToLevels(root: TreeNode | null, maxDepth: number, levels: (number | null)[][] = [], depth = 0): number[][] { // [1,2,3,4,2,4,3]  
  console.log('treeToLevels', {levels})  
  if (depth >= maxDepth) return levels  
  levels[depth] = (levels[depth] || []).concat(typeof root?.val === 'number' ? root.val : null) // [[1],[2, 2],[3,4,4,3]]  
  treeToLevels(root?.left || null, maxDepth, levels, depth + 1) // // //  
  treeToLevels(root?.right || null, maxDepth, levels, depth + 1) // // //  
  return levels  
}  
  
function isSymmetricArray(xs: (number | null)[]): boolean { // [3,4,4,3]; [2,2]; [1]  
  for (let l = 0, r = xs.length - 1; l <= r; l++, r--) {  
    if (xs[l] !== xs[r]) return false  
  }  
  return true // T; T; T  
}  
  
function isSymmetric(root: TreeNode | null): boolean { // [1,2,3,4,2,4,3]  
  if (!root) return true  
  const treeDepth = depth(root)  
  console.log({treeDepth})  
  
  const levels: number[][] = treeToLevels(root, treeDepth) // [[1],[2, 2],[3,4,4,3]]  
  console.log({levels})  
  return levels.every(isSymmetricArray) // T  
};