Implement tree column grouping and minimal parentheses fixes
Overview
This question evaluates proficiency in tree and string algorithms, specifically binary tree traversal and coordinate-based column grouping with ordering/tie-breaking semantics, as well as string processing for minimal-parentheses deletion, and probes competence with data structures, streaming/online processing, correctness guarantees, and in-place space management. It is commonly asked in the Coding & Algorithms domain to assess algorithmic reasoning, implementation-level trade-offs and complexity analysis, testing both conceptual understanding of ordering and correctness and practical application skills such as achieving linear-time and space-efficient solutions and scaling to large inputs.
Part A — Binary tree column grouping: Given the root of a binary tree, group node values by their vertical columns from leftmost to rightmost using x-coordinates (left child: x-1, right child: x+ 1). Within each column, list nodes in top-to-bottom order; if two nodes share the same row and column, order them by left-to-right encounter. Return a list of columns (each a list of integers). Describe your algorithm, the data structures used, and analyze time and space complexity. Follow-ups: (
- How would you stream results without storing the entire traversal? (
- How would you change tie-breaking to use node values instead? (
- Discuss handling trees with up to 100,000 nodes.
Part B — Minimal deletions for balanced parentheses: Given a string s of lowercase letters and parentheses '()' only, remove the fewest parentheses so the string is balanced. Return any valid resulting string. Provide an O(n) time solution and prove correctness. Follow-ups: (
- Can you do it in a single pass? (
- Can you achieve O(
- extra space if in-place edits are allowed?)