Range Sum of BST

Background Knowledge

The problem involves a Binary Search Tree (BST), which is a fundamental data structure in computer science. A BST is a tree where each node has a comparable value, and for any given node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node. This property makes BSTs useful for efficient searching, inserting, and deleting nodes. In the context of this problem, the BST is represented as a level-order array, which is a way of traversing the tree level by level, from left to right.

To solve this problem, it's essential to understand the properties of a BST and how to traverse it. Tree traversal algorithms, such as Depth-First Search (DFS) and Breadth-First Search (BFS), are used to visit each node in the tree. In the case of a BST, a DFS traversal can be particularly useful, as it allows us to visit nodes in a specific order (e.g., in-order, pre-order, or post-order). The in-order traversal of a BST visits nodes in ascending order, which can be helpful for finding nodes within a specific range.

The problem requires finding the sum of all node values within a given range [low, high]. This involves identifying the nodes that fall within the range and adding up their values. To do this efficiently, we need to leverage the properties of the BST and the traversal algorithm to minimize the number of nodes that need to be visited.