LC #545: Boundary of Binary Tree, but do in only 1 pass of Tree

?? FAANG favourite question of last year. This question teaches you to hone your edge case tackling skills.

???? Follow-up : Solving the question in 3 passes of entire tree is trivial but can you do it in just 1 pass?

? Central Concept:

• ?? We maintain 3 lists to track left_boundary, leaf_nodes, and right_boundary
• ?? And 2 variables to store the current last nodes of left_boundary and right_boundary list
• ?? If current_node is a leaf, add to leaf_boundary and then return
• ?? Then we compare the current node whether it is left_child OR right_child of BOTH, the last node of left_boundary, AND the last node of right_boundary
• ?? Be wary that a right child of left_boundary node can be a left_boundary node too!
• ?? And accordingly we add current node to either left_boundary or right_boundary and then do PreOrder Traversal
• ?? At the end we reverse the right_boundary, concatenate the root value with the 3 lists and return

? Edge Cases to be wary of:

1. ?? When root is the only input
2. ?? When root does NOT have left child: here ensure that your left_boundary is NEVER appended into
3. ?? When root does NOT have a right child: here ensure that your right_boundary is NEVER appended into

?? Overall, the follow-up question makes this a pretty challenging question so I would advise you to practice it before your coding interview.