Implement BST vertical traversal and list conversion
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given the root of a binary search tree (BST):
1) Implement vertical order traversal: assign the root column 0, left child column −1, right child column +1; return columns from leftmost to rightmost. Within each column, list node values from top to bottom, breaking ties by left-to-right order at the same depth. Provide the algorithm, data structures used, and complexity analysis.
2) Convert the BST into a sorted doubly linked list in-place (non-circular) by reusing nodes (left becomes prev, right becomes next). Return the head of the list. Discuss recursive vs iterative approaches, edge cases (empty tree, single node, skewed tree), and time/space complexity.
Quick Answer: This question evaluates proficiency with binary search trees, vertical-order traversal semantics, in-place pointer manipulation for converting a BST into a sorted doubly linked list, and algorithmic complexity analysis within the Coding & Algorithms domain.