Coding questions · Meta
Implement BST vertical traversal and list conversion
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.
Given the root of a binary search tree (BST):
- 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.
- 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.
BST Vertical Order Traversal
Given a BST as level-order values, return vertical columns from left to right in breadth-first order within each column.
Examples
Example 1
Input: ([5,3,7,2,4,6,8],)
Output: [[2], [3], [5, 4, 6], [7], [8]]
Explanation: Balanced BST.
Example 2
Input: ([],)
Output: []
Explanation: Empty tree.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.
BST to Sorted Doubly Linked List Values
Given a BST as level-order values, return the values in the sorted order that the in-place doubly linked list would contain.
Examples
Example 1
Input: ([5,3,7,2,4,6,8],)
Output: [2, 3, 4, 5, 6, 7, 8]
Explanation: Sorted in-order list.
Example 2
Input: ([1],)
Output: [1]
Explanation: Single node.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.