Learning GoLang: Algorithm to Compute the Range Sum of a Binary Search Tree

justyy (84)in #programming • 5 years ago

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.

/**
 * 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.

/**
 * 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:

--EOF (The Ultimate Computing & Technology Blog) --