Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/783.html

783. Minimum Distance Between BST Nodes (Medium)

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.

Solution 1.

• Java
• C++
• Python
• Go

• /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode(int x) { val = x; }
   * }
   */
  class Solution {
      public int minDiffInBST(TreeNode root) {
          List<Integer> inorderTraversal = inorderTraversal(root);
          int minDiff = Integer.MAX_VALUE;
          int size = inorderTraversal.size();
          for (int i = 1; i < size; i++) {
              int diff = inorderTraversal.get(i) - inorderTraversal.get(i - 1);
              minDiff = Math.min(minDiff, diff);
          }
          return minDiff;
      }
  
      public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> inorderTraversal = new ArrayList<Integer>();
          Stack<TreeNode> stack = new Stack<TreeNode>();
          TreeNode node = root;
          while (!stack.isEmpty() || node != null) {
              while (node != null) {
                  stack.push(node);
                  node = node.left;
              }
              TreeNode visitNode = stack.pop();
              inorderTraversal.add(visitNode.val);
              node = visitNode.right;
          }
          return inorderTraversal;
      }
  }
  
  ############
  
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      private int ans;
      private int prev;
      private int inf = Integer.MAX_VALUE;
  
      public int minDiffInBST(TreeNode root) {
          ans = inf;
          prev = inf;
          dfs(root);
          return ans;
      }
  
      private void dfs(TreeNode root) {
          if (root == null) {
              return;
          }
          dfs(root.left);
          ans = Math.min(ans, Math.abs(root.val - prev));
          prev = root.val;
          dfs(root.right);
      }
  }
  

• // OJ: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
  // Time: O(N)
  // Space: O(log(N))
  class Solution {
  private:
      int ans = INT_MAX;
      TreeNode *prev = NULL;
      void inorder(TreeNode *root) {
          if (!root) return;
          inorder(root->left);
          if (prev) ans = min(ans, root->val - prev->val);
          prev = root;
          inorder(root->right);
      }
  public:
      int minDiffInBST(TreeNode* root) {
          inorder(root);
          return ans;
      }
  };
  

• # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class Solution:
      def minDiffInBST(self, root: Optional[TreeNode]) -> int:
          def dfs(root):
              if root is None:
                  return
              dfs(root.left)
              nonlocal ans, prev
              ans = min(ans, abs(prev - root.val))
              prev = root.val
              dfs(root.right)
  
          ans = prev = inf
          dfs(root)
          return ans
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
      def minDiffInBST(self, root):
          """
          :type root: TreeNode
          :rtype: int
          """
          vals = []
          def inOrder(root):
              if not root:
                  return 
              inOrder(root.left)
              vals.append(root.val)
              inOrder(root.right)
          inOrder(root)
          return min([vals[i + 1] - vals[i] for i in xrange(len(vals) - 1)])
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func minDiffInBST(root *TreeNode) int {
  	inf := 0x3f3f3f3f
  	ans, prev := inf, inf
  	var dfs func(*TreeNode)
  	dfs = func(root *TreeNode) {
  		if root == nil {
  			return
  		}
  		dfs(root.Left)
  		ans = min(ans, abs(prev-root.Val))
  		prev = root.Val
  		dfs(root.Right)
  	}
  	dfs(root)
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  
  func abs(x int) int {
  	if x < 0 {
  		return -x
  	}
  	return x
  }
  

All Problems

All Solutions