Intuition and Algorithm

We traverse the tree using a depth first search. If node.val falls outside the range [L, R], (for example node.val < L), then we know that only the right branch could have nodes with value inside [L, R].

We showcase two implementations - one using a recursive algorithm, and one using an iterative one.

Recursive Implementation

Iterative Implementation

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the tree.

  • Space Complexity: , where is the height of the tree.

Analysis written by: @awice.