FastPrepBinary Tree Vertical Order Traversal

Binary Tree Vertical Order Traversal

Bloomberg LP logoBloomberg LP● MediumNEW GRADPHONE SCREENONSITE INTERVIEW
Learn

Problem statement

Given the root of a binary tree, return its vertical order traversal.

Place the root in column 0. A left child is one column to the left of its parent, and a right child is one column to the right. Return the columns from leftmost to rightmost.

Within each column, list nodes from top to bottom. If two nodes have the same row and column, preserve their left-to-right breadth-first encounter order.

Function

verticalOrder(root: TreeNode) → int[][]

Examples

Example 1

root = [3,9,20,null,null,15,7]return = [[9],[3,15],[20],[7]]

The occupied columns are -1, 0, 1, and 2. Nodes 3 and 15 share column 0 and appear from top to bottom.

Example 2

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

Nodes 5 and 6 have the same row and column. Breadth-first left-to-right order places 5 before 6.

Example 3

root = []return = []

An empty tree has no columns.

Constraints

  • The tree contains at most 1000 nodes.
  • -1000 <= Node.val <= 1000.

More Bloomberg LP problems

See Bloomberg LP hiring insights
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 * }
 */
public int[][] verticalOrder(TreeNode root) {
    // Write your code here.
}
root[3,9,20,null,null,15,7]
expected[[9],[3,15],[20],[7]]
Checking account…