CODEWITHSUNDEEP
algorithmgobinary-search-tree
IvanD
IvanD

Reputation: 2953

Minimizing memory consumption and execution time of Range Sum of Binary Tree

I need to minimize the memory consumption and the execution time of a function that calculates the Range Sum of Binary Search Tree (https://leetcode.com/problems/range-sum-of-bst/).

The current results I am having are:

Runtime: 88 ms, faster than 69.00% of Go online submissions for Range Sum of BST.

Memory Usage: 7.9 MB, less than 5.67% of Go online submissions for Range Sum of BST.

My current code:

func rangeSumBST(root *TreeNode, min int, max int) int {
    sum := 0
    arr := []*TreeNode{root}
    var node *TreeNode

    for len(arr) > 0 {
        node = arr[len(arr)-1]
        arr = arr[:len(arr)-1]
        
        if node.Val >= min && node.Val <= max {
            sum += node.Val
        }

        if node.Left != nil && node.Val > min {
            arr = append(arr, node.Left)
        }

        if node.Right != nil && node.Val < max {
            arr = append(arr, node.Right)
        }
    }

    return sum
}

I tried to solve the problem recursively, which was elegant but of course slower and more memory hungry than iterative solution.

The iterative solution I have is as lean and simple as I possibly can make it. I declare and reuse the node variable instead of declaring it inside of the for loop. I add nodes to the end of the slice instead of beginning.

What else can I do to make it faster and use less memory? Or is there a more efficient algorithm? Or is it that Leetcode measuring the execution time and memory consumption somehow incorrectly?

Upvotes: 0

Views: 423

Answers (1)

รยקคгรђשค
รยקคгรђשค

Reputation: 1979

Since it is a BST you can do in O(1) space complexity using Inorder Morris traversal for BST, you cannot do better than O(N) time complexity for single queries unless you have some kind of preprocessing in the tree itself. Your current implementation is using a stack so your current space complexity is O(N) in worst case, when tree is basically a path.

Implementation in Go (was able to beat 99%):

func rangeSumBST(root *TreeNode, min int, max int) int {
    if root == nil {
        return 0
    }
    
    var pre *TreeNode
    curr := root
    sum := 0
    for curr != nil {
        if curr.Left == nil {
            if curr.Val >= min && curr.Val <= max {
                sum += curr.Val
            }
            if curr.Val > max {
                break
            }
            curr = curr.Right
        } else {
            pre = curr.Left
            
            for pre.Right != nil && pre.Right != curr {
                pre = pre.Right
            }
            
            if pre.Right == nil {
                pre.Right = curr
                curr = curr.Left
            } else {
                pre.Right = nil
                if curr.Val >= min && curr.Val <= max {
                    sum += curr.Val
                }
                if curr.Val > max {
                    break
                }                
                curr = curr.Right
            }
            
        }
    }
    return sum
}

Time complexity: O(Number of nodes)

Space complexity: O(1)

Note: Somehow it doesn't show any improvement in memory performance, maybe because the tests are not enough and leetcode is known to show old statistics of previously submitted solutions when tests were not too big.

Upvotes: 1

Related Questions