Minimum Absolute Difference in BST (by LeetCode) and AMP!!!

-
Hello my dears,

  It has been a while since I've posted something here, so here we go. Today we'll be landing on LeetCode territory again, and we'll deal with Binary Search Trees and In-Order Traversal. But first, some news: Bing has shipped AMP (Accelerated Mobile Pages) on m.bing.com. Yeahhh! We had done this work before on the Bing iOS and Android native apps, but now we're rolling it out to the browser (m.bing.com), so whenever you search for any query that triggers a News article, sure enough you shall see the famous AMP icon there, and the pages will load much faster than the non-AMP ones. Very cool project done by my team:


Now back to LeetCode. The problem in question is this: https://leetcode.com/problems/minimum-absolute-difference-in-bst/#/description, or copied/pasted here:

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.
It is important to use the only crucial information in this problem: that we're dealing with a Binary-Search-Tree (BST). With that information in mind, remember that an In-Order traversal of the tree will give you all its elements in sorted order. If your tree for instance is:
  6
3  7
The In-Order traversal will give you 3,6,7. Now with that it becomes very easy to solve it:
a) Do an In-Order traversal passing in the previous value
b) The processing will consist of checking <current value> - <previous value> and keeping tracking of the min
Linear time, very fast as the response indicates. Code is down below - cheers! Marcelo

    public class Solution
    {
        public int GetMinimumDifference(TreeNode root)
        {
            int minDiff = Int32.MaxValue;
            int previousValue = -1;
            GetMinDiffInOrder(root, ref previousValue, ref minDiff);
            return minDiff;
        }

        private void GetMinDiffInOrder(TreeNode currentNode,
                                       ref int previousValue,
                                       ref int minDiff)
        {
            if (currentNode == null) return;

            GetMinDiffInOrder(currentNode.left, ref previousValue, ref minDiff);
            if (previousValue >= 0 && currentNode.val - previousValue < minDiff) minDiff = currentNode.val - previousValue;
            previousValue = currentNode.val;
            GetMinDiffInOrder(currentNode.right, ref previousValue, ref minDiff);
        }
    }

Comments

  1. TarasJune 24, 2017 at 8:59 PM

    Congrats on your launch Marcelo and awesome to see some new posts from you! This time I have nothing to remove, so according to Antoine de Saint-Exupery you've achieved perfection :)

    Just for completeness adding my C++ solution:
    class Solution {
    public:
    int getMinimumDifference(const TreeNode* root) {
    int previous = -1;
    int min_so_far = numeric_limits::max();
    function traverse = [&](const TreeNode* current) {
    if (current->left) traverse(current->left);
    if (previous != -1) {
    min_so_far = min(min_so_far, current->val - previous);
    }
    previous = current->val;
    if (current->right) traverse(current->right);
    };
    traverse(root);
    return min_so_far;
    }
    };

    Have a fabulous weekend and thanks for posting!

    ReplyDelete
  2. Marcelo M De BarrosJune 24, 2017 at 9:00 PM

    Lovely!!!!!

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

Prompt Engineering and LeetCode

-
Image
With AI it becomes super interesting to try to "guide" it to solve a coding (LeetCode) problem. An example would be this one here:  The Knight’s Tour - LeetCode 2664. The Knight’s Tour Medium 11 0 Add to List Share Given two positive integers  m  and  n  which are the height and width of a  0-indexed  2D-array  board , a pair of positive integers  (r, c)  which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the  board  gets visited  exactly  once (the starting cell is considered visited and you  shouldn't  visit it again). Return  the array   board   in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight). Note that a  knight  can  move  from cell  (r1, c1)  to cell  (r2, c2)  if  0 <= r2 <= m - 1  and  0 <= c2 <= n - 1  and  min(abs(r1 - r2), abs(c1 - c2)) = 1  and  max(abs(r1 - r2), abs(c1 - c2)) = 2 .  
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more