BinarySearch 0134 Count BST Nodes in a Range

Problem statement

https://binarysearch.com/problems/Count-BST-Nodes-in-a-Range/

Solution

Variation of Leetcode 0938. Range Sum of BST.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root, low, high):
        def dfs(node):
            if not node: return
            if low <= node.val <= high: self.out += 1
            if node.val > low:  dfs(node.left)
            if node.val < high: dfs(node.right)
                
        self.out = 0
        dfs(root)
        return self.out