Minimum Distance Between BST Nodes

-
Love problems like this one: https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.
Example :
Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.
Note:
  1. The size of the BST will be between 2 and 100.
  2. The BST is always valid, each node's value is an integer, and each node's value is different.
The key here is to remember that in a Binary Search Tree, the elements are sorted when you traverse it using in-order traversal. With this information in mind, it becomes trivial: in-order traversal keeping track of the min diff. Some usage of "long" just to avoid corner cases. Code is below, thanks, Boris.


public class Solution
{
 public int MinDiffInBST(TreeNode root)
 {
  long previousVal = Int64.MinValue;
  long minDiff = Int64.MaxValue;
  _MinDiffInBST(root, ref previousVal, ref minDiff);
  return (int)minDiff;
 }

 public void _MinDiffInBST(TreeNode node,
        ref long previousVal,
        ref long minDiff)
 {
  if (node == null) return;
  _MinDiffInBST(node.left, ref previousVal, ref minDiff);
  minDiff = (previousVal != Int64.MinValue) ? Math.Min(minDiff, node.val - previousVal) : minDiff;
  previousVal = node.val;
  _MinDiffInBST(node.right, ref previousVal, ref minDiff);
 }
}

Comments

  1. TarasJanuary 27, 2019 at 11:35 AM

    Very nice! Another great thing about Python for lazy people like me is that I never have to think about longs :)

    class Solution:
    def minDiffInBST(self, root):
    state = [None, 10 ** 9]

    def helper(node):
    if not node:
    return
    helper(node.left)
    prev, min_diff = state
    if prev:
    min_diff = min(min_diff, node.val - prev)
    state[0], state[1] = node.val, min_diff
    helper(node.right)

    helper(root)
    return state[1]

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more