Solve tree traversal and interval merging tasks
Overview
This question evaluates algorithmic problem-solving and data-structure competency, focusing on binary tree traversal and column-wise ordering (including BFS versus DFS trade-offs) as well as interval merging and sorting strategies for scheduling.
Part A — Column-wise Binary Tree Grouping: You are given the root of a binary tree. Group nodes by vertical column index, where the root has column 0, the left child of a node at column c has column c−1, and the right child has column c+1. Within each column, list nodes from top to bottom; for nodes that share the same row and column, order them from left to right. Return a list of columns from leftmost to rightmost, each containing the ordered node values. Explain and compare BFS versus DFS for this task (ordering guarantees, memory usage, recursion depth), state which you would implement and why, and analyze time and space complexity. Discuss edge cases such as skewed trees and very deep trees.
Part B — Merge Meeting Time Ranges: You are given a list of half-open intervals [start, end) representing meeting times during a day. Merge all overlapping or touching intervals and return the condensed schedule sorted by start time. Describe an O(n log n) approach for unsorted input and a single-pass O(n) approach if the input is already sorted by start. Specify the data structures you will use, how you handle zero-length intervals and endpoint inclusivity/exclusivity, and provide time and space complexity.