how to get difference between two values or nodes in javascript

Question

I am trying to solve this problem .I am not getting expected output

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.

I tried like this

var minDiffInBST = function (root) {
    let min = Number.MAX_VALUE
    const getMin = (node) => {
        if (node.left && node.right) {
            console.log('both')
            return Math.min(node.val - node.left.val, node.right.val - node.val)
        } else if (node.right) {
            console.log('right')
            return node.right.val - node.val
        } else if (node.left) {
            console.log('left')
            return node.val - node.left.val
        } else {
            return Number.MAX_VALUE
        }
    }

    const preOrder = (root) => {
        if (!root) {
            return 0;
        }
        let x = getMin(root)
        if (x < min)
            min = x
        preOrder(root.left)
        preOrder(root.right)

    }
    preOrder(root)
    return min
};

console.log(minDiffInBST({
        "val": 90,
        "left": {
            "val": 69,
            "left": {"val": 49, "left": null, "right": {"val": 52, "left": null, "right": null}},
            "right": {"val": 89, "left": null, "right": null}
        },
        "right": null
    }

))

Getting output 3 expected output 1

question I am taken from here https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Answer 1

In addition to Paul Nikonowicz comment here is my implementation in C++, using inorder traversal to get a sorted vector of the BST and then iterating it comparing each consequent values to the maximum value of the vector

#include<iostream> 
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    vector<int> toCompare = {};

    /* find min diff pair of our inorder derived vector*/
    int find_min(vector <int> const& a) {
        int diff = *std::max_element(a.begin(), a.end());
        for (int i = 0; i < a.size()-1; i++)
            if (a.at(i + 1) - a.at(i) < diff) {
                diff = a.at(i + 1) - a.at(i);

            }
        return diff;
    }

    int minDiffInBST(TreeNode* root) {
   
        if (root == NULL) {
            return 0;
        };

        /* In order traversal */
        minDiffInBST(root->left);
        /* Storing in vector/list */
        toCompare.push_back(root->val);

        minDiffInBST(root->right);
 
        return find_min(toCompare);    
      
    };
};


int main() {
    struct TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(3);
    
    Solution myObj;

    cout << myObj.minDiffInBST(root);
    return 0;

Answer 2

You need to do an in order traversal, not a pre order traversal.

In a BST, an inorder traversal gives you a sorted list. In a sorted list, the minimum distance between two elements will be closest to each other.

So, solve this for a sorted list first, and then solve it for a BST traversed IN ORDER