LeetCode 938 - Range Sum of BST

https://leetcode.com/problems/range-sum-of-bst/

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R(inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

https://leetcode.com/problems/range-sum-of-bst/discuss/192019/Java-3-recursive-methods-with-comment.

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0; // base case.
        if (root.val < L) return rangeSumBST(root.right, L, R); // left branch excluded.
        if (root.val > R) return rangeSumBST(root.left, L, R); // right branch excluded.
        return root.val + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R); // count in both children.
    }

The following are two more similar recursive codes.

Method 2:

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0; // base case.
        return (L <= root.val && root.val <= R ? root.val : 0) + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R);

Method 3:

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) { return 0; }
        int sum = 0;
        if (root.val > L) { sum += rangeSumBST(root.left, L, R); } // left child is a possible candidate.
        if (root.val < R) { sum += rangeSumBST(root.right, L, R); } // right child is a possible candidate.
        if (root.val >= L && root.val <= R) { sum += root.val; } // count root in.
        return sum;
    }

https://leetcode.com/problems/range-sum-of-bst/discuss/193674/Jave-easy-to-understand-2ms-solution-(tree-pruning)

    int sum = 0;
    public int rangeSumBST(TreeNode root, int L, int R) {
        helper(root, L, R);
        return sum;
    }
    
    public void helper(TreeNode root, int L, int R){
        if(root == null){
            return;
        }
        if(root.val <= R && root.val >= L){
            sum += root.val;
            helper(root.left, L, R);
            helper(root.right, L, R);
        }else if(root.val < L){
            helper(root.right, L, R); //no need to go left since the left branch must be smaller than L
        }else{ //root great than R
            helper(root.left, L, R); //no need to go right since the right branch must be larger than R
        }
    }




  int ans;

  public int rangeSumBST(TreeNode root, int L, int R) {

    ans = 0;

    dfs(root, L, R);

    return ans;

  }

  public void dfs(TreeNode node, int L, int R) {

    if (node != null) {

      if (L <= node.val && node.val <= R)

        ans += node.val;

      if (L < node.val)

        dfs(node.left, L, R);

      if (node.val < R)

        dfs(node.right, L, R);

    }

  }

  public int rangeSumBST(TreeNode root, int L, int R) {

    int ans = 0;

    Stack<TreeNode> stack = new Stack();

    stack.push(root);

    while (!stack.isEmpty()) {

      TreeNode node = stack.pop();

      if (node != null) {

        if (L <= node.val && node.val <= R)

          ans += node.val;

        if (L < node.val)

          stack.push(node.left);

        if (node.val < R)

          stack.push(node.right);

      }

    }

    return ans;

  }