Solution
Approach 1: Depth First Search
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.