Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].
GoLang Implementation: Range Sum of a BST via Stack
In Go, we use an list to implement the stack. And we can push the left and/or right branches if it is still falling within the current range.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func rangeSumBST(root *TreeNode, low int, high int) int { if root == nil { return 0 } var st = make([]*TreeNode, 0) var ans = 0 st = append(st, root) for len(st) > 0 { var sz = len(st) var cur = st[sz - 1] st = st[:sz - 1] if cur == nil { continue } if cur.Val >= low && cur.Val <= high { ans += cur.Val } if cur.Val > low { st = append(st, cur.Left) } if cur.Val < high { st = append(st, cur.Right) } } return ans } |
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, low int, high int) int {
if root == nil {
return 0
}
var st = make([]*TreeNode, 0)
var ans = 0
st = append(st, root)
for len(st) > 0 {
var sz = len(st)
var cur = st[sz - 1]
st = st[:sz - 1]
if cur == nil {
continue
}
if cur.Val >= low && cur.Val <= high {
ans += cur.Val
}
if cur.Val > low {
st = append(st, cur.Left)
}
if cur.Val < high {
st = append(st, cur.Right)
}
}
return ans
}GoLang Implementation: Range Sum of a BST via Recursion
With Recursion, we can recursively sum up the nodes in the left and right tree respectively that are within the range [low, high]. The time complexity is also O(N). Space complexity is O(N) where N is the number of the nodes in the Binary Search Tree – each node is visited once.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func rangeSumBST(root *TreeNode, low int, high int) int { if root == nil { return 0 } var ans = 0 if low <= root.Val && root.Val <= high { ans += root.Val } if root.Val >= low { ans += rangeSumBST(root.Left, low, high) } if root.Val <= high { ans += rangeSumBST(root.Right, low, high) } return ans } |
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, low int, high int) int {
if root == nil {
return 0
}
var ans = 0
if low <= root.Val && root.Val <= high {
ans += root.Val
}
if root.Val >= low {
ans += rangeSumBST(root.Left, low, high)
}
if root.Val <= high {
ans += rangeSumBST(root.Right, low, high)
}
return ans
}See also other implementations of the Range Sum of BST in other programming languages:
– Teaching Kids Programming – Algorithms to Compute the Range Sum of a Binary Search Tree
– How to Sum within A Range in a Binary Search Tree?
– GoLang: Algorithm to Compute the Range Sum of a Binary Search Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Largest Anagram Group
Next Post: Teaching Kids Programming - Longest Common Prefix Algorithm
