PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

Solve binary tree, grid, and heap tasks 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.

  • Medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

Solve binary tree, grid, and heap tasks

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Answer the following independent coding tasks: 1) Range sum in a BST: Given the root of a binary search tree and integers low and high, return the sum of all node values v where low <= v <= high. Implement using DFS with BST pruning and analyze time/space complexity. 2) Lowest common ancestor: Given the root of a (not-necessarily-BST) binary tree and two existing nodes p and q, return their lowest common ancestor. Discuss recursive and iterative approaches and their complexities. 3) Minimum round-trip flight cost: You are given two lists—departures = [(date_i, price_i)] and returns = [(date_j, price_j)]. Choose one departure and one return such that return_date > depart_date and the total price is minimized. If the lists are already sorted by date, design an O(n) algorithm; otherwise, describe an O(n log n) approach. Return the chosen pair and the minimal total cost, or indicate no feasible pair. 4) Node equals subtree average: Given a binary tree, count how many nodes have a value equal to the integer average of all values in their subtree (including the node itself), where average is defined as floor(sum / size). Provide an O(n) solution. 5) 0/1 image cluster and border: Given a binary grid (0/ 1) and a starting cell (r, c), return all cells that are 4-directionally connected to (r, c) and have the same value as grid[r][c]. Follow-up: return the set of coordinates of all cells that are 4-directional neighbors of this component but are not part of it (the component’s border neighbors). Analyze complexity and discuss BFS vs DFS trade-offs. 6) Validate max-heap binary tree: Given a binary tree, determine whether it is a valid max-heap by checking both completeness (levels filled left to right with no gaps) and the heap-order property (each node’s value >= its children’s values). Implement an O(n) BFS-based check and explain why a naive DFS can fail on completeness.

Quick Answer: Solve binary tree, grid, and heap tasks 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.

Range Sum of a BST (DFS with pruning)

You are given a binary search tree encoded as a **level-order list** `tree` (using `null`/`None` placeholders for missing children), plus integers `low` and `high`. Return the sum of all node values `v` with `low <= v <= high`. Use the BST ordering to prune: if a node's value is `<= low` you never need its left subtree, and if it's `>= high` you never need its right subtree. **Input format:** `tree` is the level-order array (children skipped when their parent slot is absent). `low`, `high` are inclusive bounds. **Output:** the integer sum.

Constraints

  • 0 <= number of nodes <= 10^4
  • Node values and low, high fit in a 32-bit integer
  • The tree satisfies the BST property
  • low <= high

Examples

Input: ([10, 5, 15, 3, 7, None, 18], 7, 15)

Expected Output: 32

Explanation: In-range values are 10, 7, and 15 -> 32. Node 18 and 3 are excluded.

Input: ([10, 5, 15, 3, 7, 13, 18, 1, None, 6], 6, 10)

Expected Output: 23

Explanation: In-range values: 10, 7, 6 -> 23.

Input: ([], 1, 10)

Expected Output: 0

Explanation: Empty tree sums to 0.

Input: ([5], 5, 5)

Expected Output: 5

Explanation: Single node inside the inclusive bound.

Input: ([5], 6, 10)

Expected Output: 0

Explanation: Single node outside the range.

Hints

  1. DFS (stack or recursion) is the natural fit for subtree aggregation.
  2. Prune: only recurse left when node.val > low; only recurse right when node.val < high.
  3. Add node.val to the running sum exactly when low <= node.val <= high.

Lowest Common Ancestor in a Binary Tree

Given a binary tree encoded as a **level-order list** `tree` (with `null`/`None` placeholders) and the **values** `p` and `q` of two nodes that exist in the tree, return the value of their lowest common ancestor (LCA). The tree is **not** necessarily a BST, so you cannot use ordering shortcuts. Node values are assumed unique for this challenge. **Recursive idea:** an LCA is the deepest node that finds `p` in one subtree and `q` in the other (or is itself `p`/`q` with the other below it).

Constraints

  • 2 <= number of nodes <= 10^4
  • Node values are unique
  • p and q are distinct values that both exist in the tree
  • The tree may be arbitrary (not a BST)

Examples

Input: ([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], 5, 1)

Expected Output: 3

Explanation: 5 is in the left subtree, 1 in the right; their LCA is the root 3.

Input: ([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], 5, 4)

Expected Output: 5

Explanation: 4 is a descendant of 5, so 5 is its own ancestor and the LCA.

Input: ([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], 7, 4)

Expected Output: 2

Explanation: Both 7 and 4 are children of node 2.

Input: ([1, 2], 1, 2)

Expected Output: 1

Explanation: 2 is a child of the root 1.

Input: ([1], 1, 1)

Expected Output: 1

Explanation: Degenerate p == q on the only node.

Hints

  1. Recurse: if a node equals p or q, return it upward.
  2. If both the left and right recursive calls return non-null, the current node is the LCA.
  3. Otherwise propagate up whichever side found a target.
  4. Alternative: BFS to build a child->parent map, walk p's ancestors into a set, then walk q's ancestors until one is in the set.

Minimum Round-Trip Flight Cost

You are given two lists, `departures` and `returns`, each a list of `[date, price]` pairs. Choose exactly one departure and one return such that **return_date > depart_date** and the total `depart_price + return_price` is minimized. Return `[depart_date, return_date, total_cost]` for the optimal pair, or `None`/`null` if no feasible pair exists. **O(n log n)** general solution: sort both by date, sweep returns in date order while maintaining the cheapest departure seen with an earlier date. If the inputs are already sorted, the sweep alone is **O(n)**. **Tie-breaking note:** when multiple pairs share the minimal total, this reference keeps the cheapest earlier-seen departure (smallest date among equal-price departures) and the earliest qualifying return.

Constraints

  • 0 <= len(departures), len(returns) <= 10^5
  • dates and prices are non-negative integers
  • A valid pair requires return_date strictly greater than depart_date
  • Return None/null when no return date is later than any departure date

Examples

Input: ([[1, 100], [3, 50], [5, 200]], [[2, 80], [4, 40], [6, 300]])

Expected Output: [3, 4, 90]

Explanation: Depart day 3 ($50) + return day 4 ($40) = $90, the cheapest feasible combination.

Input: ([[1, 100]], [[2, 200]])

Expected Output: [1, 2, 300]

Explanation: Only one feasible pair.

Input: ([[5, 10]], [[1, 10]])

Expected Output: null

Explanation: The only return date (1) precedes the only departure date (5): infeasible.

Input: ([], [[1, 10]])

Expected Output: null

Explanation: No departures.

Input: ([[1, 100], [2, 90], [3, 80]], [[1, 50]])

Expected Output: null

Explanation: The lone return date 1 is not strictly after any departure date.

Input: ([[10, 5], [2, 100]], [[3, 1], [11, 1]])

Expected Output: [10, 11, 6]

Explanation: For return day 11 the cheapest earlier departure is day 10 ($5): total $6, beating return day 3 (forced to depart day 2 at $100).

Hints

  1. Sort departures and returns by date.
  2. Sweep returns in increasing date order; before pricing a return, fold in every departure with an earlier date and track the minimum departure price so far.
  3. The minimum departure price is monotonic as the return date grows, giving an O(n) sweep after sorting.
  4. Guard the infeasible case: if no departure precedes any return, answer is None.

Count Nodes Equal to Subtree Average

Given a binary tree as a **level-order list** `tree` (with `null`/`None` placeholders), count how many nodes have a value equal to the **integer average** of all values in that node's subtree, including the node itself. The average is `floor(subtree_sum / subtree_size)`. A single post-order DFS computes, for each node, the sum and size of its subtree in O(1) from its children's results, giving an overall O(n) solution.

Constraints

  • 0 <= number of nodes <= 10^4
  • Node values fit in a 32-bit integer (use 64-bit accumulators for subtree sums)
  • Average is floor(sum / size)
  • Leaf nodes always satisfy the condition (avg of one value is the value)

Examples

Input: ([4, 8, 5, 0, 1, None, 6],)

Expected Output: 5

Explanation: Leaves 0, 1, 6 qualify; node 5's subtree {5,6} avg 5; root's subtree sum 24/6 = 4. Node 8's subtree {8,0,1} avg 3 != 8. Total 5.

Input: ([1],)

Expected Output: 1

Explanation: Single leaf: average equals its own value.

Input: ([],)

Expected Output: 0

Explanation: Empty tree.

Input: ([5, 3, 7],)

Expected Output: 3

Explanation: Leaves 3 and 7 qualify; root subtree sum 15/3 = 5 == 5.

Input: ([10, 2, 2],)

Expected Output: 2

Explanation: Both leaf 2s qualify; root 14/3 = 4 != 10.

Input: ([2, 1, 4],)

Expected Output: 3

Explanation: Leaves 1 and 4 qualify; root 7/3 floor = 2 == 2.

Hints

  1. Post-order DFS: return (sum, size) for each subtree.
  2. At each node, sum = left_sum + right_sum + val and size = left_size + right_size + 1.
  3. Increment the counter when sum // size == node.val (floor division).
  4. Use 64-bit accumulators to avoid overflow on large subtrees in typed languages.

0/1 Image Cluster and Border Neighbors

Given a binary grid `grid` (cells 0 or 1) and a starting cell `(r, c)`, return the connected component and its border. Return `[component, border]` where: - `component` = the sorted list of `[row, col]` cells 4-directionally connected to `(r, c)` and sharing the value `grid[r][c]`. - `border` = the sorted list of in-bounds cells that are 4-directional neighbors of the component but are **not** part of it. Both lists are sorted by `(row, col)`. This is a flood-fill (BFS or DFS) plus a neighbor sweep.

Constraints

  • 1 <= R, C <= 1000
  • Each grid cell is 0 or 1
  • 0 <= r < R and 0 <= c < C for a valid start
  • Connectivity is 4-directional (up/down/left/right)

Examples

Input: ([[1, 1, 0], [1, 0, 0], [0, 0, 1]], 0, 0)

Expected Output: [[[0, 0], [0, 1], [1, 0]], [[0, 2], [1, 1], [2, 0]]]

Explanation: The 1-component is the L-shape at (0,0),(0,1),(1,0); its in-bounds non-component neighbors are (0,2),(1,1),(2,0).

Input: ([[1]], 0, 0)

Expected Output: [[[0, 0]], []]

Explanation: Single cell, no neighbors, empty border.

Input: ([[0, 0], [0, 0]], 1, 1)

Expected Output: [[[0, 0], [0, 1], [1, 0], [1, 1]], []]

Explanation: All zeros are one component covering the whole grid; no border cells exist.

Input: ([[1, 0, 1], [0, 1, 0], [1, 0, 1]], 1, 1)

Expected Output: [[[1, 1]], [[0, 1], [1, 0], [1, 2], [2, 1]]]

Explanation: The center 1 is isolated; its four orthogonal neighbors are all border cells.

Input: ([[1, 1, 1]], 0, 1)

Expected Output: [[[0, 0], [0, 1], [0, 2]], []]

Explanation: The whole single row is one component; no in-bounds non-component neighbors.

Hints

  1. Flood-fill from (r, c), expanding only into neighbors with the same value.
  2. Track component membership in a visited set so border detection can test 'not in component'.
  3. For the border, scan each component cell's 4 in-bounds neighbors and collect those outside the component (dedup with a set).
  4. BFS uses a queue (bounded by frontier width); DFS uses the call stack (risk of overflow on huge components) - both are O(R*C).

Validate a Max-Heap Binary Tree (BFS)

Given a binary tree as a **level-order list** `tree` (with `null`/`None` placeholders preserving the actual shape), determine whether it is a valid **max-heap**. Two conditions must both hold: 1. **Completeness:** every level is fully filled left-to-right, with no internal gaps (a missing child may only be followed by other missing nodes). 2. **Heap order:** every node's value is `>=` each of its children's values. Do a level-order BFS: once you dequeue a missing child (a gap), any later real node violates completeness; check the heap-order property against each present child as you go. **Why naive DFS struggles:** a depth-first traversal sees node values and parent-child order fine, but it has no global left-to-right level view, so detecting an internal gap (a hole earlier in a level than a filled slot) requires extra index bookkeeping that BFS gets for free.

Constraints

  • 0 <= number of nodes <= 10^4
  • An empty tree is treated as a valid (vacuous) max-heap
  • Completeness means no real node appears after a missing slot in BFS order
  • Heap order compares each node against its present children only

Examples

Input: ([9, 7, 8, 3, 6, 2, 1],)

Expected Output: true

Explanation: Complete tree and every parent >= its children.

Input: ([9, 7, 8, 3, 6],)

Expected Output: true

Explanation: Last level filled left-to-right with no gaps; heap order holds.

Input: ([9, 10, 8],)

Expected Output: false

Explanation: Child 10 exceeds parent 9, breaking heap order.

Input: ([9, 7, 8, None, 6],)

Expected Output: false

Explanation: A real node (6) follows a missing slot in level order, breaking completeness.

Input: ([5],)

Expected Output: true

Explanation: Single node is trivially a valid max-heap.

Input: ([],)

Expected Output: true

Explanation: Empty tree is vacuously valid.

Input: ([9, 7, 8, 3, 3, 8, 8],)

Expected Output: true

Explanation: Ties allowed: parent >= child includes equality.

Hints

  1. Use BFS and enqueue both children (even null ones) so gaps surface in order.
  2. Maintain a 'seen a gap' flag; if you later dequeue a real node after a gap, completeness is violated.
  3. For heap order, fail fast if any child's value exceeds its parent's value.
  4. An empty tree and a single node are both valid max-heaps.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Shortest Unique Prefixes - Meta (medium)
  • Compute Exclusive Execution Times - Meta (medium)
  • Solve Tree Columns And Maze Variants - Meta (medium)
  • Solve Tree Diameter and Palindromic Counts - Meta (medium)
  • Simulate Monster Team Battles - Meta (hard)