Approach 1: Store Locations
It's evident that there are two steps in a straightforward solution: first, find the location of every node, then report their locations.
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
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.
Time Complexity: , where is the number of nodes in the given tree.
Space Complexity: .
Analysis written by: @awice.