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 depthfirst 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 (x1, 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.