Top View of a Binary Tree
Updated
Problem statement
You are given a binary tree serialized in level order as levelOrder. Each entry is either an integer written as a string or "null".
Assign horizontal distance 0 to the root. A left child has its parent's distance minus 1, and a right child has its parent's distance plus 1. For each horizontal distance, the first node reached in level order is visible from above.
Return the visible node values from the smallest horizontal distance to the largest. Return an empty array for an empty tree.
Function
topView(levelOrder: String[]) → int[]Examples
Example 1
levelOrder = ["1","2","3","null","4","null","5"]return = [2,1,3,5]The first visible nodes at horizontal distances -1, 0, 1, and 2 are 2, 1, 3, and 5.
Example 2
levelOrder = ["10","5","15","2","7","12","20"]return = [2,5,10,15,20]The topmost values are read from the far-left horizontal distance through the far-right distance.
Example 3
levelOrder = []return = []An empty tree has no visible nodes.
Constraints
0 <= levelOrder.length <= 10^5- Every non-null entry is a valid 32-bit signed integer.
- The serialization describes one valid binary tree in level order.
More Capillary Technologies Onsite Interview questions
Similar questions at other companies
- Zigzag Level-Order TraversalFlipkart · ONSITE INTERVIEW
- Binary Tree Zigzag Level Order TraversalLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
- Binary Tree Zigzag Level Order TraversalMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Binary Tree Level-Order Traversal by LevelsAdobe · PHONE SCREEN · ONSITE INTERVIEWAdobe interview questions
- Breadth-First Values of a Binary TreeFigma · ONSITE INTERVIEWFigma interview questions
- Independent Level Iterators Over a Shared Binary TreeGoogle · PHONE SCREENGoogle interview questions
- Binary Tree Spiral Level OrderAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Diameter of an Acyclic Undirected GraphSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Binary Tree Nodes at Distance KApple · ONSITE INTERVIEWApple interview questions
- Bottom View of a Binary TreeOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions