# Leetcode 783. Minimum Distance Between BST Nodes
###### tags: `leetcode` `daily`

[題目連結](https://leetcode.com/problems/minimum-distance-between-bst-nodes/)

# Method
:::info
:bulb: **作法講解**:
concept: using DFS algorithm, traversal all of the node,
for each node, we will do three things
first, initialize "min_val" to node's val
"max_val" to node's val

second, if node's left child not NULL,
traversal to left child, we will get the minimum value and maximum value in left child subtree.
and compute minimum difference with node's val minus maximum value in left child subtree,
and set "min_val" to the minimum value in left child subtree

third, if node's right child not NULL,
traversal to right child, we will get the minimum value and maximum value in right child subtree.
and compute minimum difference with minimum value in right child subtree minus node's val,
and set "max_val" to the maximum value in right child subtree

final, return "min_val" and "max_val"
:::

TC: O(N) SC: O(h)
:::spoiler 完整程式碼

/**
 * Definition for a binary tree node.
 * 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:
    pair<int, int> get_min_max_value(TreeNode *root, int &ans)
    {
        int min_val = root->val;
        int max_val = root->val;
        if(root->left) {
            pair<int, int> p = get_min_max_value(root->left, ans);
            ans = min(ans, root->val - p.second);
            min_val = min(min_val, p.first);
        }

        if(root->right) {
            pair<int, int> p = get_min_max_value(root->right, ans);
            ans = min(ans, p.first - root->val);
            max_val = max(max_val, p.second);
        }

        return {min_val, max_val};
    }
    int minDiffInBST(TreeNode* root) 
    {
        int ans = INT32_MAX;
        get_min_max_value(root, ans);
        return ans;
    }
};

:::