FastPrep
Problem · Tree

Top View of a Binary Tree

Learn this problem
● MediumInMobi logoInMobiFULLTIMEONSITE INTERVIEW

Problem statement

Given the root of a non-empty binary tree, return its top view from left to right.

Assign horizontal distance 0 to the root. A left edge decreases horizontal distance by 1, and a right edge increases it by 1. For every horizontal distance, the visible node is the node with minimum depth.

If two nodes have the same minimum depth and horizontal distance, choose the one reached first by a level-order traversal that enqueues each left child before its right child.

Function

topView(root: TreeNode) → int[]

Examples

Example 1

root = [1,2,3,4,5,6,7]return = [4,2,1,3,7]

The first visible nodes at horizontal distances -2 through 2 are 4, 2, 1, 3, 7.

Example 2

root = [1,2,3,null,4,5,null]return = [2,1,3]

Nodes 4 and 5 share horizontal distance 0 below the root, so the root hides both.

Constraints

  • The tree contains between 1 and 10^5 nodes.
  • -10^9 <= node.val <= 10^9

More InMobi problems

drafts saved locally
public int[] topView(TreeNode root) {
    // write your code here
}
root[1,2,3,4,5,6,7]
expected[4,2,1,3,7]
checking account