783. Minimum Distance Between BST Nodes.md

783. Minimum Distance Between BST Nodes

---

Difficulty : Easy

Related Topics : Tree、Recursive

---

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:

• The size of the BST will be between 2 and 100.
• The BST is always valid, each node's value is an integer, and each node's value is different.
• This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

---

Solution

• mine
  • Java

    • sort Runtime: 1 ms, faster than 21.67%, Memory Usage: 37 MB, less than 6.67% of Java online submissions

      // O(N*LogN)time O(N)space
      // N is the node count
      public int minDiffInBST(TreeNode root) {
          List<Integer> list = new ArrayList<>();
          dfs(root,list);
          if(list.size() == 0){
              return 0;
          }
          int res = Integer.MAX_VALUE;;
          Collections.sort(list);
          for(int i = 1; i < list.size(); i++){
              res = Math.min(res, list.get(i) - list.get(i - 1));
          }
          return res;
      
      }
      public void dfs(TreeNode node, List<Integer> list){
          if(node != null){
              list.add(node.val);
              dfs(node.left, list);
              dfs(node.right, list);
          }
      }
      

    • Iterate & LinkedList Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.6 MB, less than 6.67% of Java online submissions

      // O(N)time O(N)space
      // N is the node count
      public int minDiffInBST(TreeNode root) {
          LinkedList<Integer> list = new LinkedList<>();
          LinkedList<TreeNode> nodes = new LinkedList<>();
          TreeNode cur =  root;
          while(cur != null || !nodes.isEmpty()){
              if(cur != null){
                  if(cur.left != null){
                      nodes.push(cur);
                      cur = cur.left;
                  }else{
                      list.add(cur.val);
                      cur = cur.right;
                  }
              }else{
                  cur = nodes.pop();
                  list.add(cur.val);
                  cur = cur.right;
              }
          }
          int res = Integer.MAX_VALUE;
          int pre = list.removeFirst();
          while(!list.isEmpty()){
              res = Math.min(res,list.getFirst() - pre);
              pre = list.removeFirst();
          }
          return res;
      }
      

---

• the most votes

• Recursive Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.7 MB, less than 60.00% of Java online submissions

  // O(N)time O(D)space
  // N is the node count
  // D is the root deep
  class Solution {
      Integer res = Integer.MAX_VALUE, pre = null;
      public int minDiffInBST(TreeNode root) {
          if (root.left != null) minDiffInBST(root.left);
          if (pre != null) res = Math.min(res, root.val - pre);
          pre = root.val;
          if (root.right != null) minDiffInBST(root.right);
          return res;
      }
  }
  

---

• the leetcode's solution

• Recursive Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.9 MB, less than 6.67% of Java online submissions

  // O(N)time O(D)space
  // N is the node count
  // D is the root deep
  class Solution {
      Integer prev, ans;
      public int minDiffInBST(TreeNode root) {
          prev = null;
          ans = Integer.MAX_VALUE;
          dfs(root);
          return ans;
      }
  
      public void dfs(TreeNode node) {
          if (node == null) return;
          dfs(node.left);
          if (prev != null)
              ans = Math.min(ans, node.val - prev);
          prev = node.val;
          dfs(node.right);
      }
  }
  

---