Welcome to Subscribe On Youtube

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

530. Minimum Absolute Difference in BST

Level

Easy

Description

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.

Solution

First obtain the inorder traversal of the binary search tree, which contains all the values in the binary search tree in sorted order. Then calculate absolute differences between each pair of adjacent values in the inorder traversal, and return the minimum absolute difference.

• 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 getMinimumDifference(TreeNode root) {
          List<Integer> inorderTraversal = inorderTraversal(root);
          int minimumDifference = Integer.MAX_VALUE;
          int size = inorderTraversal.size();
          for (int i = 1; i < size; i++)
              minimumDifference = Math.min(minimumDifference, inorderTraversal.get(i) - inorderTraversal.get(i - 1));
          return minimumDifference;
      }
  
      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;
      }
  }
  

• // OJ: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
  // Time: O(N)
  // Space: O(logN)
  class Solution {
  public:
      int getMinimumDifference(TreeNode* root) {
          int prev = -1, ans = INT_MAX;
          function<void(TreeNode*)> dfs = [&](TreeNode *root) {
              if (!root) return;
              dfs(root->left);
              if (prev != -1) ans = min(ans, root->val - prev);
              prev = root->val;
              dfs(root->right);
          };
          dfs(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 getMinimumDifference(self, root: 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 getMinimumDifference(self, root):
      """
      :type root: TreeNode
      :rtype: int
      """
      self.val = None
      self.ans = float("inf")
  
      def inorder(root):
        if not root:
          return
        inorder(root.left)
        if self.val is not None:
          self.ans = min(self.ans, abs(root.val - self.val))
        self.val = root.val
        inorder(root.right)
  
      inorder(root)
      return self.ans
  
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func getMinimumDifference(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