Skills101
← All coding problems

Bottom View of Binary Tree

mediumTrees & BST II+20 XPTime limit 2s

Now look at the tree from below. In every column you see only the node closest to the bottom. Print the values you see, from the leftmost column to the rightmost.

Columns. Put the root in column 0. A left child is one column to the left of its parent (column − 1), a right child one column to the right (column + 1). In each column you see the node on the lowest level (largest depth); if two nodes of that level share the column, you see the one that comes last in level order (the more right one in the drawing).

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one tree.

Output: the visible values on one line, left to right, or empty for an empty tree.

Constraints: 0 ≤ nodes ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: the mirror of the top view. Do a BFS that remembers each node's column, and simply overwrite the map entry every time you meet a column again — the last write in BFS order wins.

Sample input 1

20 8 22 5 3 null 25 null null 10 14

Sample output 1

5 10 3 14 25

Sample input 2

1 2 3 4 5 6 7

Sample output 2

4 2 6 3 7

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.