[Java] DFS & BFS - With explanation
DFS\n\nclass Solution {\n    public int rangeSumBST(TreeNode root, int low, int high) {\n        if(root == null)\n            return 0;\n        int sum = root
**DFS**\n```\nclass Solution {\n    public int rangeSumBST(TreeNode root, int low, int high) {\n        if(root == null)\n            return 0;\n        int sum = root.val <= high && root.val >= low ? root.val : 0;\n        int left = 0;\n        int right = 0;\n        if(root.left != null){\n            left = rangeSumBST(root.left,low,high);\n        } \n        if(root.right != null){\n            right = rangeSumBST(root.right, low, high);\n        }\n        return sum + left + right;\n    }\n}\n```\n**BFS**\n```\nclass Solution {\n    public int rangeSumBST(TreeNode root, int low, int high) {\n        if(root == null)\n            return 0;\n        Queue<TreeNode> q = new LinkedList<TreeNode>();\n        q.add(root); // add root node\n        int sum = 0;\n        while(!q.isEmpty()){\n            int itr = q.size();\n            while(itr > 0){\n                TreeNode dummy = q.poll();\n                sum += (dummy.val >= low && dummy.val <= high) ? dummy.val : 0;\n                if(dummy.left != null)\n                    q.add(dummy.left);\n                if(dummy.right != null)\n                    q.add(dummy.right);\n                itr--;\n            }\n        }\n\t\treturn sum;\n\t}\n}\n```\n   \n**PROBLEM OVERVIEW**\nWe are essentially tasked with finding the sum of all nodes whose values are between the inclusive range [low,high].\n\n**SOLUTION ASSESSMENT**\nThe first things that come to mind are any tree-traversla algorithms (I have an inclination to utilize DFS or BFS, and I will show both approaches)\n\n**PSEUDOCODE RECURSION DFS**\n```\npublic int rangeSumBST(TreeNode root, int low, int high) {\n1. If(root == null) return 0;\n2. sum = node.val if within [low,high] : 0;\n3. int leftSum = rangeSum(node.left,low,high); //left node\n4. int rightSum = rangeSum(node.right,low,high); //right node\n5. return sum + leftSum + rightSum\n}\n```\n\nThe heart of this solution lies with the recursive calls in lines 3-4. It will essentially visit all the nodes in the left branch and* return the leftSum* and all the right nodes in the branch and return the rightSum. Finally, the answer will be the current node + left + right.\n\n**PSUEDOCODE ITERATIVE BFS**\n```\n1. if root is null return 0; // corner case\n2. initialize Queue<TreeNode> q and int sum\n3. add root to q\n4. while q is not empty {\n\t5. itr = q.size() // this is because the current "size" is the # of elements in that row\n\t6. while itr > 0\n\t\t7. get node from list and add to answer if sum is in range\n\t\t8. add left and right nodes if they exist\n}\n9. return sum\n```\nIn the BFS solution, the current Queue of TreeNodes is read in FIFO order, so it maintains an order (not that it matters in this problem). \nThe key steps lie in 5 and 7-8; for 5 regulates the number of iterations in that particular "row" of the tree, which is the current size of the Queue. Line 7-8 add the children of that current row in left -> order.\n\n**TIME COMPLEXITY**\nThe code for both runs in O(n) time complexity because it always visits every node.\nNOTE: even though BFS solution has nested while loops, they are only called a maximum of n times, where n is the number of nodes in the tree.\n\n\n
['Tree', 'Recursion', 'Java']