Katkat
Back

Solve tree traversal and two-pointer problems

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Solve tree traversal and two-pointer problems evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement the following independent problems:

  1. Vertical columns: Given a binary tree, return lists of node values grouped by vertical columns from leftmost to rightmost. For nodes in the same column and row, preserve left-to-right order of appearance. State time and space complexities. Follow-up: support streaming insertions and queries.
  2. Right-side view: Given a binary tree, return the sequence of nodes visible from the right side. Clarify tie-breaking and how to handle missing children. Provide BFS and DFS solutions and their complexities.
  3. Two-sum pairs count: Given a sorted integer array and target T, count the number of unique index pairs (i, j), i < j, such that nums[i] + nums[j] == T. Achieve O(n) time and O(
  4. extra space; handle duplicates robustly.
  5. Zigzag levels: Given a binary tree, output its level-order traversal with alternating left-to-right and right-to-left ordering per level. Discuss trade-offs between deque-based BFS and DFS with level tracking.