CodeSnatch Logo
 ██████╗ ██████╗ ██████╗ ███████╗    ███████╗███╗   ██╗ █████╗ ████████╗ ██████╗██╗  ██╗██╔════╝██╔═══██╗██╔══██╗██╔════╝    ██╔════╝████╗  ██║██╔══██╗╚══██╔══╝██╔════╝██║  ██║██║     ██║   ██║██║  ██║█████╗      ███████╗██╔██╗ ██║███████║   ██║   ██║     ███████║██║     ██║   ██║██║  ██║██╔══╝      ╚════██║██║╚██╗██║██╔══██║   ██║   ██║     ██╔══██║╚██████╗╚██████╔╝██████╔╝███████╗    ███████║██║ ╚████║██║  ██║   ██║   ╚██████╗██║  ██║ ╚═════╝ ╚═════╝ ╚═════╝ ╚══════╝    ╚══════╝╚═╝  ╚═══╝╚═╝  ╚═╝   ╚═╝    ╚═════╝╚═╝  ╚═╝

Learn · Earn · Connect

Practice Problem

Minimum Absolute Difference in BST

Difficulty: Medium

Given a BST, find the minimum absolute difference between the values of any two different nodes using in-order traversal.

Minimum Absolute Difference in BST

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Examples

Example 1:

Input: root = [4, 2, 6, 1, 3]
Output: 1

      4
     / \
    2   6
   / \
  1   3

Explanation: The minimum absolute difference is 1 (between nodes 1 and 2, or 2 and 3, or 3 and 4).

Example 2:

Input: root = [1, 0, 48, null, null, 12, 49]
Output: 1

      1
     / \
    0  48
       / \
     12  49

Explanation: The minimum absolute difference is 1 (between nodes 0 and 1).

Example 3:

Input: root = [236, 104, 701, null, 227, null, 911]
Output: 9

Explanation: The sorted values are [104, 227, 236, 701, 911]. The minimum difference is 236 - 227 = 9.

Constraints

  • The number of nodes in the tree is in the range [2, 10^4].
  • 0 <= Node.val <= 10^5

Expected Complexity

  • Time: O(n)
  • Space: O(h) where h is the height of the tree
MEDIUM
Binary Tree
Binary Search Tree (BST)
DFS
Inorder
Intermediate

0 views

Solution

Hints

Hint 1
Hint 2
Premium
Hint 3
Premium
Hint 4
Premium
All Problems