How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at BlackRock.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at BlackRock during technical interviews.

Traverse a tree and answer 2D prefix sums | BlackRock Coding Question

Q: Traverse a tree and answer 2D prefix sums

This question evaluates a candidate's competency in tree traversal and array preprocessing, specifically in-order traversal of binary trees and 2D prefix-sum techniques for answering submatrix-sum queries.

Traverse a tree and answer 2D prefix sums

Company: BlackRock

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given two independent coding tasks. ## Task 1: In-order traversal of a binary tree Given the root of a binary tree, return the in-order traversal of its node values. - **In-order** means: traverse left subtree → visit node → traverse right subtree. - **Input:** `root` (may be `null`) - **Output:** an array/list of node values in in-order - **Constraints (typical):** up to ~10^5 nodes; values fit in 32-bit int. ## Task 2: Sum of the top-left submatrix up to (x, y) Given an `m x n` matrix `A` of integers and coordinates `(x, y)` (0-indexed), compute the sum of all elements in the rectangle from `(0,0)` to `(x,y)` inclusive. Example: `sum(x,y) = Σ_{i=0..x} Σ_{j=0..y} A[i][j]` - **Input:** matrix `A`, and one or more queries `(x, y)` where `0 ≤ x < m`, `0 ≤ y < n` - **Output:** for each query, return the computed sum - **Follow-up (common):** If there are many queries, design for fast per-query time. - **Constraints (typical):** `m,n` up to ~10^3 or higher; values can be negative; sums may require 64-bit integer type.

Quick Answer: This question evaluates a candidate's competency in tree traversal and array preprocessing, specifically in-order traversal of binary trees and 2D prefix-sum techniques for answering submatrix-sum queries.

In-order Traversal of a Binary Tree

Given the root of a binary tree, return the **in-order** traversal of its node values. In-order means: recursively traverse the **left** subtree, then **visit the current node**, then recursively traverse the **right** subtree. To keep the input marshalable, the tree is supplied as a **level-order list** (LeetCode style): index 0 is the root, and the children of the node at array position `k` follow in breadth-first order. A `None` / `null` entry means there is no node in that position (and that branch is not expanded further). An empty list means an empty tree. **Examples** - `level_order = [1, None, 2, 3]` represents the tree `1` with right child `2`, whose left child is `3`. In-order = `[1, 3, 2]`. - `level_order = [4, 2, 6, 1, 3, 5, 7]` is a complete BST. In-order = `[1, 2, 3, 4, 5, 6, 7]`. **Input:** `level_order` — a list of node values (with `None`/`null` for absent nodes). **Output:** a list of the node values in in-order. **Constraints:** up to ~10^5 nodes; values fit in a 32-bit signed integer.

Constraints

0 <= number of nodes <= 10^5
Node values fit in a 32-bit signed integer
An empty list represents an empty tree (return an empty list)
None / null entries in the level-order list mark absent nodes

Examples

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

Expected Output: [1, 3, 2]

Explanation: Root 1 has only a right child 2; node 2's left child is 3. Left of 1 is empty, visit 1, then in 2's subtree go left to 3 first, then 2.

Input: ([],)

Expected Output: []

Explanation: Empty tree yields an empty traversal.

Input: ([1],)

Expected Output: [1]

Explanation: Single node: no left, visit it, no right.

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

Expected Output: [1, 2, 3, 4, 5, 6, 7]

Explanation: A complete BST; in-order traversal of a BST yields sorted values.

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

Expected Output: [1, 3, 2]

Explanation: Root 3, left child 1, right child 2: visit left (1), node (3), right (2).

Input: ([5, 3, 8, 1, 4, None, 9],)

Expected Output: [1, 3, 4, 5, 8, 9]

Explanation: Node 8 has no left child (None) and right child 9; in-order: 1,3,4 (left subtree), 5 (root), then 8, 9 (right subtree).

Hints

In-order = left, node, right. A recursive solution is the most direct; an iterative one uses an explicit stack to avoid deep recursion on a 10^5-node skewed tree.
First reconstruct the tree from the level-order list with a BFS queue: pop a parent, attach its next two (non-null) entries as left and right children.
For the iterative traversal: push left children until you hit null, pop and record a node, then move to its right child and repeat.

2D Prefix Sum (Top-Left Submatrix Queries)

Given an `m x n` matrix `A` of integers and a list of queries `(x, y)` (0-indexed), compute for **each** query the sum of all elements in the rectangle from `(0, 0)` to `(x, y)` **inclusive**: ``` sum(x, y) = Σ_{i=0..x} Σ_{j=0..y} A[i][j] ``` Return a list with one sum per query, in the same order as the queries. With many queries, recomputing each sum directly costs O(m·n) per query. Instead, build a **2D prefix-sum table** once in O(m·n), after which every query is answered in O(1). **Example** ``` A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] queries = [(0,0), (1,1), (2,2)] -> [1, 12, 45] ``` `sum(1,1) = 1+2+4+5 = 12`; `sum(2,2)` is the whole matrix = 45. **Input:** `matrix` (`m x n` list of lists of ints) and `queries` (list of `(x, y)` pairs with `0 <= x < m`, `0 <= y < n`). **Output:** a list of integers, one sum per query. **Constraints:** `m, n` up to ~10^3 or higher; values may be negative; sums may exceed 32-bit range, so use 64-bit integers.

Constraints

1 <= m, n (matrix may also be empty -> all sums are 0)
0 <= x < m and 0 <= y < n for every query
Matrix values may be negative
Sums may exceed 32-bit range; use 64-bit integers

Examples

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

Expected Output: [1, 12, 45, 12, 6]

Explanation: sum(0,0)=1; sum(1,1)=1+2+4+5=12; sum(2,2)=whole matrix=45; sum(2,0)=1+4+7=12 (first column); sum(0,2)=1+2+3=6 (first row).

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

Expected Output: [5]

Explanation: Single-cell matrix; the only sum is the cell itself.

Input: ([[-1, -2], [-3, -4]], [[0, 0], [0, 1], [1, 0], [1, 1]])

Expected Output: [-1, -3, -4, -10]

Explanation: All-negative matrix: sum(0,0)=-1; sum(0,1)=-1-2=-3; sum(1,0)=-1-3=-4; sum(1,1)=-1-2-3-4=-10.

Input: ([[2, -1, 3], [0, 4, -2]], [[1, 2], [0, 1], [1, 0]])

Expected Output: [6, 1, 2]

Explanation: Mixed signs: sum(1,2)=2-1+3+0+4-2=6; sum(0,1)=2-1=1; sum(1,0)=2+0=2.

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

Expected Output: [4000000000]

Explanation: Four cells of 1e9 sum to 4e9, which overflows 32-bit signed range, confirming 64-bit accumulation is required.

Input: ([], [])

Expected Output: []

Explanation: Empty matrix with no queries returns an empty list.

Hints

Naively summing the rectangle for each query is O(m·n) per query — too slow when there are many queries.
Define pre[i+1][j+1] = sum of the submatrix from (0,0) to (i,j). It satisfies pre[i+1][j+1] = A[i][j] + pre[i][j+1] + pre[i+1][j] - pre[i][j] (inclusion-exclusion).
With that table, the answer to a top-left query (x, y) is simply pre[x+1][y+1]. The 1-based padding row/column avoids special-casing the first row and column.

Quick Overview

This question evaluates a candidate's competency in tree traversal and array preprocessing, specifically in-order traversal of binary trees and 2D prefix-sum techniques for answering submatrix-sum queries.