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
We showcase two implementations - one using a recursive algorithm, and one using an iterative one.
Time Complexity: , where is the number of nodes in the tree.
Space Complexity: , where is the height of the tree.
Analysis written by: @awice.