Stokastik

Machine Learning, AI and Programming

Tag: Binary Search Tree

LeetCode : Count of Range Sum

Problem Statement Solution : This one looks like a very simple problem at first glance but I found it to be quite tricky during implementation. The straightforward solution is to pre-compute the prefix sums S(i), i.e. the sum of all integers from 0 to i-th index for all possible i, and then compute all possible range sums S(i, j), which is the sum of all integers from index i to […]

Continue Reading →

LeetCode : Recover Binary Search Tree

Problem Statement Solution : One approach that uses O(n) extra space, is to store for each node N, the pointer to the nodes with minimum and maximum values in the sub-tree rooted at N. Let's denote the minimum node rooted at N by N.min and the maximum  node by N.max. Then for a sub-tree rooted at N, the sub-tree has a "defect", if : N.val < N.left.max.val and/or N.val > N.right.min.val […]

Continue Reading →