Solution


Approach 1: Store Locations

Intuition

It's evident that there are two steps in a straightforward solution: first, find the location of every node, then report their locations.

Algorithm

To find the location of every node, we can use a depth-first search. During the search, we will maintain the location (x, y) of the node. As we move from parent to child, the location changes to (x-1, y+1) or (x+1, y+1) depending on if it is a left child or right child. [We use y+1 to make our sorting by decreasing y easier.]

To report the locations, we sort them by x coordinate, then y coordinate, so that they are in the correct order to be added to our answer.

Please see the inline comments for more details.

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the given tree.

  • Space Complexity: .


Analysis written by: @awice.