Golang Naive Solution (DFS) and Optimal (DFS+Binary Search Tree Features) | Beats 100%
\n# 1. Naive solution\n\nNaive solution that does not exploit the features of the binary search tree is the usual DFS (alternate traversal of all nodes with sel
\n# 1. Naive solution\n\nNaive solution that does not exploit the features of the binary search tree is the usual DFS (alternate traversal of all nodes with selection of matching nodes according to the condition).\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nfunc rangeSumBST(root *TreeNode, low int, high int) int {\n    if root == nil{\n        return 0\n    }\n\n    if root.Val>= low && root.Val<=high{\n        return root.Val + rangeSumBST(root.Left, low, high)+rangeSumBST(root.Right, low, high)\n    }else{\n        return rangeSumBST(root.Left, low, high)+rangeSumBST(root.Right, low, high)\n    }\n}\n```\n\n\n# 2. Optimal Solution\n\nSince we are working with a **binary search tree**, we can exploit its **features**.\nIf **node.Val < low** then we may not even consider the part of the tree that lies to the **left of this node**. \nSimilarly, if **node.Val > high** then we may not even consider the part of the tree that lies to the **right of this node**. \nIf node fits the condition **(low<=node.Val<=high)**, then we bypass both the left and right parts, as in the first solution. (adding node.Val to the answer).\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(log(n))$$\n\n# Code\n```\nfunc rangeSumBST(root *TreeNode, low int, high int) int {\n    if root == nil{\n        return 0\n    }\n    if root.Val < low{ //the root < left, so we don\'t need to go to the left\n        return rangeSumBST(root.Right, low, high)\n    }else if root.Val <=high{\n        return root.Val + rangeSumBST(root.Left, low, high)+rangeSumBST(root.Right, low, high) // root fits, we go to left and right\n    } else{\n        return rangeSumBST(root.Left, low, high) //root > high, so we don\'t need to go to the right\n    }    \n}\n```\n## If you hava any question, feel free to ask. If you like the solution or the explaination, Please UPVOTE!\n
['Depth-First Search', 'Binary Search Tree', 'Binary Tree', 'Go']