Katkat
Back

Compute vertical order of a BST

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of binary tree traversals and coordinate-based ordering, including tie-breaking by breadth-first visitation order, plus competency in algorithmic time and space complexity analysis and strategies for handling deep recursion and streaming large inputs.

Compute the vertical order traversal of a binary search tree. Define coordinates so the root is at column 0, row 0; the left child is (col−1, row+

  1. and the right child is (col+1, row+ 1). Return a list of columns from the smallest to the largest column index, where each column is a list of node values ordered by increasing row. For nodes that share the same (row, column), break ties by the order they would be visited in a left-to-right breadth-first traversal. Provide an algorithm, justify its time and space complexity, and implement a function that returns the required structure. Follow-ups: (
  2. How would you handle extremely skewed trees to avoid worst-case recursion depth? (
  3. How would you stream results if the tree is too large to fit in memory?