Home > Reflections | ⏮️ ⏭️

2024-06-24

🏋️ Coding Practice

199. Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

🪞 Reflections

1. This is a very similar problem to what I saw in a real interview about a week ago
2. that previous exposure seems to have been enough for a flawless performance today
3. < 21 minutes isn’t bad for a medium problem
4. manually testing recursive functions is still a bit cumbersome
5. representing trees in manual tests is still a bit cumbersome
6. running 2 manual tests seemed like a good strategy here
   1. the first was for good coverage of a tricky case (a tree where the rightmost node was sometimes in a left branch
   2. the second was a simple null test, covering a common edge case
7. having a 3rd check, explicitly for null checks didn’t take much time and seems valuable to incorporate into my general strategy
   1. This pass reminds me of static analysis: it takes less time to do than a dynamic test, we pay attention to fewer things, it’s good for catching limited classes of bugs
   2. I wonder if there are other classes of manual “static analysis” that would be useful to incorporate
   3. Perhaps a manual type checking phase could be useful, where I ensure that I’m using values according to their types. This seems like good motivation to add more explicit type annotations to my code.
8. While I forgot to annotate the time required for planning, it didn’t take long. Seems like a good balance of succinct yet thorough enough to get the main ideas in place (though I didn’t explicitly call out recursion in my plan… perhaps because I was already anticipating using this based on prior exposure to a very similar problem) and support proper big-O complexity analysis.
9. A second pass to refactor and simplify yielded a much shorter, simpler implementation.
10. Implementing the iterative version is good practice
    1. in the iterative loop, push on the stack in reverse order to recursive calls from the recursive version
    2. refactorings from the recursive version can be mapped to analogous refactorings in the iterative version
    3. The bug found in the iterative version should have been caught by my test.
       1. I must have been mentally popping elements off of the stack in the order I wanted them to come out in (i.e. sometimes from the top and sometimes from the bottom) instead of the order dictated by the code.
       2. 🤔 I wonder what the appropriate systematic compensation is for this kind of error.
       3. Maybe I was a bit too loose with my test state annotations, relying too heavily on my working memory and mental shortcuts.
       4. Or maybe I was simply too quick to assume the result of the .pop() operation, and to compensate I should habitually be more dilligent about simulating operations instead of taking mental shortcuts.
       5. Or maybe this error is best thought of as a bit of random variation to be expected in the long run and the current speed to rigor ratio is appropriate for interview contexts. i.e. common cause variation and not special cause variation.
11. Extra type annotations don’t take much time to write and seem like a helpful addition to my usual routine (in support of an occasional type-checking, manual, static-analysis pass).
12. Reviewing the official solutions after implementing my ideas yielded some approaches I hadn’t considered and inspired mutation-minimizing implementations.

⌨️ My Solutions

/* return the nodes of a binary tree visible from the right  
1. we want to return the right-most element of each level of the tree  
  
Plan:  
1. convert the tree to levels  
2. get the rightmost element of each level  
  
time complexity: O(N) in the number of nodes in the tree  
extra space complexity: O(N) to store each level and the result  
[9:25] done with initial implementation  
[17:11] done with first test  
[19:11] done with 2nd test  
[20:45] done with null checks  
no bugs found during manual testing  
[20:56] successful submission  
no bugs found after manual testing  
*/  
/**  
 * 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 treeToLevels(root: TreeNode | null, depth = 0, levels: TreeNode[][] = []): TreeNode[][] { // null 0 []; {v:4} 1 [...]; {v:3} 2 [[1],[2]]; {v:2,r:{v:3}} 1 [1]; {v:1,l:{v:2,r:{v:3}},r:{v:4}} 0 []  
  if (root) { // null check  
    levels[depth] = (levels[depth] || []).concat(root) // [[1],[2,4],[3]] // null check  
    if (root.left) { // null check  
      treeToLevels(root.left, depth + 1, levels) // [[1]]  
    }  
    if (root.right) { // null check  
      treeToLevels(root.right, depth + 1, levels) //  
    }  
  }  
  return levels // []; [[1],[2,4],[3]]  
}  
  
function rightSideView1(root: TreeNode | null): number[] { // null; {v:1,l:{v:2,r:{v:3}},r:{v:4}}  
  const levels = treeToLevels(root) // []; [[1],[2,4],[3]]  
  const rightMostNodes = levels.map(level => level[level.length - 1]) // []; [1,4,3] // we won't ever have nulls in this array  
  const rightMostValues = rightMostNodes.map(node => node.val) // []; [1,4,3] // we won't ever have nulls in this array  
  return rightMostValues // []; [1,4,3]  
};  
  
/* simplifications  
1. instead of maintaining each level, we can only return the rightmost value of each level by overwriting the value of the result array at that level  
note: this only works if we ensure that further-right nodes are assessed after futher-left nodes  
2. this avoids the need for transformation after recursion  
3. we can remove the explicit left and right null-checks since they'll be checked in a recursive call anyway  
Wow! Look how short and simple this implementation is!  
Notes:  
1. This was untimed, but didn't take very long  
2. I did no manual testing, but there were no bugs  
*/  
function rightSideView2(root: TreeNode | null, level = 0, result: number[] = []): number[] {  
  if (root) {  
    result[level] = root.val  
    rightSideView2(root.left, level + 1, result)  
    rightSideView2(root.right, level + 1, result)  
  }  
  return result  
};  
  
/* iterative version with explicit stack  
Bugs found after initial implementation, 1 test, and first submission  
1. wrong answer: [1,2,3,null,5,null,4] -> [1,2,5] (expected: [1,3,4])  
Fix: push the right side before the left side so that right side is popped later  
*/  
function rightSideView3(root: TreeNode | null): number[] { // {1,2,null,3,4}  
  const result: number[] = []  
  const stack: [TreeNode, number][] = []  
  if (root) stack.push([root, 0]) // [{1},0]  
  while (stack.length) {  
    const [node, level]: [TreeNode, number] = stack.pop() // {4},1; {3},2; {2},1; {1},0  
    result[level] = node.val // [1,4,3]; [1,2,3]; [1,2]; [1] // null-check: we never push null nodes on the stack, so null is always defined to look for a val  
    if (node.right) stack.push([node.right, level + 1]) // [[{4},1],[{3},2]]; [[{2},1],[{4},1]]  
    if (node.left) stack.push([node.left, level + 1]) // [[{2},1]]  
  }  
  return result // [1,4,3]  
};  
  
/* refactor & simplify iterative version  
1. consolidate some null checks  
Notes:  
1. not sure if this is actually better than above, but it does require fewer null checks  
2. this is an analogous refactor to one performed on the recursive version (which was inspiration for this)  
*/  
function rightSideView4(root: TreeNode | null): number[] {  
  const result: number[] = []  
  const stack: [TreeNode | null, number][] = []  
  stack.push([root, 0])  
  while (stack.length) {  
    const [node, level]: [TreeNode | null, number] = stack.pop()  
    if (node) {  
      result[level] = node.val  
      stack.push([node.right, level + 1])  
      stack.push([node.left, level + 1])  
    }  
  }  
  return result  
};  
  
/* After reviewing the official solutions... A recursive version that minimizes mutation  
1. always recurse right-side first  
2. only push an element if we're at the max depth seen so far  
*/  
function rightSideView5(root: TreeNode | null, level = 0, result: number[] = []): number[] {  
  if (root) {  
    if (result.length === level) result.push(root.val)  
    rightSideView5(root.right, level + 1, result)  
    rightSideView5(root.left, level + 1, result)  
  }  
  return result  
};  
  
/* An iterative, mutation-minimizing version  
*/  
function rightSideView(root: TreeNode | null): number[] {  
  const result: number[] = []  
  const stack: [TreeNode, number][] = []  
  if (root) stack.push([root, 0])  
  while (stack.length) {  
    const [node, depth]: [TreeNode, number] = stack.pop()  
    if (depth === result.length) result.push(node.val)  
    if (node.left) stack.push([node.left, depth + 1])  
    if (node.right) stack.push([node.right, depth + 1])  
  }  
  return result  
};