Home > Reflections | ⏮️ ⏭️

2024-06-26

🏋️ Coding Practice

545. Boundary of Binary Tree

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary.
The left boundary is the set of nodes defined by the following:

• The root node’s left child is in the left boundary. If the root does not have a left child, then the left boundary is empty.
• If a node in the left boundary and has a left child, then the left child is in the left boundary.
• If a node is in the left boundary, has no left child, but has a right child, then the right child is in the left boundary.
• The leftmost leaf is not in the left boundary.
  The right boundary is similar to the left boundary, except it is the right side of the root’s right subtree. Again, the leaf is not part of the right boundary, and the right boundary is empty if the root does not have a right child.
  The leaves are nodes that do not have any children. For this problem, the root is not a leaf.
  Given the root of a binary tree, return the values of its boundary.

🪞 Reflections

1. 52 minutes is a long time
   1. 8:20 is too long for planning
   2. finishing the first implementation in ~12 minutes isn’t bad, but there were a couple of bugs
   3. testing took a long time, but it found several bugs
   4. But this is a pretty complicate problem, so maybe it’s not too bad
2. I’m happy with the bugs I caught during manual testing
3. The bug I didn’t catch during manual testing was a careless mistake
   1. I didn’t think about ordering the nodes properly on my first pass of the high-level implementation
   2. and I didn’t notice that my test result was not what it should have been (in terms of the order of nodes) at the end of testing
   3. but I was able to recognize the issue immediately and fixed it in one shot
4. I’m happy with my recursive implementations
5. I feel like working with trees is getting more natural

⌨️ My Solutions

/* Return the values of the boundary of the tree  
Boundary =  
1. root  
2. left boundary (left subtree of root + leftmost, non-leaf nodes in left subtree)  
3. leaves  
4. right boundary (analogous to left boundary)  
  
Approaches:  
1. walk the tree 3 times to get the left boundary, right boundary, and leaves - O(N)  
2. walk the tree once, pushing elements into either left boundary, right boundary, or leaf arrays - O(N)  
  
Approach 1 is a bit slower due to multiple passes, but it may be simpler code, thus better in an interview context.  
[8:20] Done planning  
[20:58] Done with initial implementation  
Bugs found during manual testing:  
1. left boundary: including inner right nodes  
[31:01] done fixing leftBoundary  
2. leafNodes: error detecting root node  
[37:17] done fixing leafNodes  
[44:57] done with test  
Bugs found during null checks  
1. pushed node instead of node.val into nodes array in leafNodes function  
[48:20] done fixing leafNodes  
[49:05] first automated test  
Wrong Answer: [1,null,2,3,4] -> [1,2,3,4] (expected [1,3,4,2])  
Ah.. correct nodes, wrong order  
[52:30] Fixed  
[52:37] 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)  
 *     }  
 * }  
 */  
  
const isLeaf = (node: TreeNode): boolean => !node.left && !node.right  
  
function leftBoundary(root: TreeNode, boundary: number[] = []): number[] { // [2,4,5,null,null,7,8]; [1,2,3,4,5,6,null,null,null,7,8,9,10]  
  if (root.left) {  
    if (isLeaf(root.left)) {  
      return boundary // [2]  
    } else {  
      boundary.push(root.left.val) // [2]  
      leftBoundary(root.left, boundary) //  
    }  
  } else if (boundary.length && root.right && !isLeaf(root.right)) {  
    boundary.push(root.right.val)  
    leftBoundary(root.right, boundary)  
  }  
  return boundary  
}  
  
function rightBoundary(root: TreeNode, boundary: number[] = []): number[] { // [6,9,10]; [3,6,null,9,10]; [1,2,3,4,5,6,null,null,null,7,8,9,10]  
  if (root.right) {  
    if (isLeaf(root.right)) {  
      return boundary // [3,6]  
    } else {  
      boundary.push(root.right.val) // [3]  
      rightBoundary(root.right, boundary) //  
    }  
  } else if (boundary.length && root.left && !isLeaf(root.left)) {  
    boundary.push(root.left.val) // [3,6]  
    rightBoundary(root.left, boundary) //  
  }  
  return boundary  
}  
  
function leafNodes(root: TreeNode, nodes: number[] = [], first = true): number[] { // [10]; [9]; [6,9,10]; [3,6,null,9,10]; [8]; [7]; [5,7,8]; [4]; [2,4,5,null,null,7,8]; [1,2,3,4,5,6,null,null,null,7,8,9,10]  
  if (!first && isLeaf(root)) {  
    nodes.push(root.val) // [4,7,8,9,10]; [4,7,8,9]; [4,7,8]; [4,7]; [4]  
  }  
  if (root.left) leafNodes(root.left, nodes, false) // // // // //  
  if (root.right) leafNodes(root.right, nodes, false) // // // //  
  return nodes // [4,7,8,9,10]  
}  
  
function boundaryOfBinaryTree(root: TreeNode | null): number[] { // [1,2,3,4,5,6,null,null,null,7,8,9,10]  
  if (!root) return []  
  const boundary: number[] = [  
    root.val, // 1  
    ...leftBoundary(root), // [2]  
    ...leafNodes(root), // [4,7,8,9,10]  
    ...rightBoundary(root).reverse(), // Correct: [6,3]; Bug: [3,6]  
  ]  
  return boundary // Correct: [1,2,4,7,8,9,10,6,3]; Bug: [1,2,3,6,4,7,8,9,10]  
};