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 Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

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

Compute BST range sum | Meta Coding Question

Compute BST range sum

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given the root of a binary search tree and two integers low and high (inclusive), compute the sum of values of all nodes with low <= val <= high. Provide both recursive and iterative solutions that prune branches using BST properties, and analyze time and space complexity.

Quick Answer: This question evaluates understanding of binary search tree properties, traversal techniques, and the ability to implement both recursive and iterative algorithms while reasoning about time and space complexity.

You are given a binary search tree (BST) encoded as a **level-order array** `tree`, where `tree[i]` is the value at position `i` and `None` marks a missing node. For any node at index `i`, its left child is at index `2*i + 1` and its right child is at index `2*i + 2`. You are also given two integers `low` and `high`. Return the sum of the values of all nodes whose value lies in the inclusive range `[low, high]` (i.e. `low <= val <= high`). Because the tree is a BST, you can prune entire subtrees: at a node with value `v`, if `v < low` you never need to descend left, and if `v > high` you never need to descend right. **Example** ``` tree = [10, 5, 15, 3, 7, None, 18], low = 7, high = 15 ``` The tree is: ``` 10 / \ 5 15 / \ \ 3 7 18 ``` Nodes in [7, 15] are 7, 10, 15 -> sum = 32. Return `32`.

Constraints

0 <= number of nodes <= 2 * 10^4
Each node value fits in a 32-bit signed integer
All node values in the BST are distinct
-10^9 <= low <= high <= 10^9
The input array is a valid level-order encoding of a BST (None marks a missing child)

Examples

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

Expected Output: 32

Explanation: Tree rooted at 10 with children 5 and 15; values in [7,15] are 7, 10, 15 -> 7+10+15 = 32.

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

Expected Output: 23

Explanation: Values in [6,10] are 6, 7, 10 -> 6+7+10 = 23. The subtrees rooted at 13/15/18 and at 3 (mostly) are pruned by BST bounds.

Input: ([], 1, 10)

Expected Output: 0

Explanation: Empty tree: there are no nodes, so the range sum is 0.

Input: ([5], 5, 5)

Expected Output: 5

Explanation: Single node 5 with low = high = 5; 5 is in range, so the sum is 5.

Input: ([5], 6, 10)

Expected Output: 0

Explanation: Single node 5 is below the range [6,10], so nothing is summed -> 0.

Input: ([8, 3, 10, 1, 6, None, 14], 100, 200)

Expected Output: 0

Explanation: Every node value (1,3,6,8,10,14) is far below [100,200]; all right descents would still fall short, so the sum is 0.

Input: ([8, 3, 10, 1, 6, None, 14], -5, 50)

Expected Output: 42

Explanation: All six nodes (1+3+6+8+10+14) lie inside [-5,50], so the sum is 42.

Hints

Use the BST ordering to avoid visiting subtrees that cannot contain in-range values: at a node with value v, skip the left subtree when v <= low and skip the right subtree when v >= high.
With the array encoding, the left child of index i is at 2*i+1 and the right child is at 2*i+2 — recurse on those indices instead of pointer children.
Handle the empty tree (empty array or a None root) by returning 0 before any traversal.
An iterative version can replace recursion with an explicit stack of indices, applying the same two pruning checks before pushing a child.

Quick Overview

This question evaluates understanding of binary search tree properties, traversal techniques, and the ability to implement both recursive and iterative algorithms while reasoning about time and space complexity.