530. Minimum Absolute Difference in BST

Description

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.

Example 1:

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

Example 2:

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

Constraints:

The number of nodes in the tree is in the range [2, 10⁴].
0 <= Node.val <= 10⁵

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Solutions

Solution 2: Explicit-Stack Inorder

Thinking

The minimum pairwise difference on a general tree needs all pairs. In a BST, inorder is sorted, so the minimum lies between adjacent values. Recursing inorder and subtracting the predecessor is correct on a short tree.

The tree can contain $10^4$ nodes. A left chain makes this walk recurse once per node and overflow the call stack.

Each node only needs the previous value. The walk does not need a return value, as long as the left subtree is finished before the node and the right subtree comes after.

An explicit stack performs that inorder walk. On entry it pushes an exit marker and the left child; on exit it updates the answer with the current value minus the predecessor and pushes the right child. The predecessor starts at $-\infty$, so the first node does not become the answer.

The minimum difference between any two node values of a binary search tree is the minimum gap between adjacent values in its increasing inorder sequence.

An explicit stack walks the tree in that order, and $\textit{pre}$ stores the previous value, initially $-\infty$. On entry we push an exit marker and the left child. On exit we update the answer with the current value minus $\textit{pre}$, store the current value in $\textit{pre}$, and push the right child.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary search tree.

/**
 * 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 getMinimumDifference(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);
    }
}


// Solution 2
/**
 * 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 static class Frame {
        TreeNode node;
        int state;

        Frame(TreeNode node, int state) {
            this.node = node;
            this.state = state;
        }
    }

    public int getMinimumDifference(TreeNode root) {
        final int inf = 1 << 30;
        int ans = inf;
        int pre = -inf;
        if (root == null) {
            return ans;
        }
        Deque<Frame> stk = new ArrayDeque<>();
        stk.push(new Frame(root, 0));
        while (!stk.isEmpty()) {
            Frame cur = stk.pop();
            TreeNode node = cur.node;
            if (cur.state == 0) {
                stk.push(new Frame(node, 1));
                if (node.left != null) {
                    stk.push(new Frame(node.left, 0));
                }
                continue;
            }
            ans = Math.min(ans, node.val - pre);
            pre = node.val;
            if (node.right != null) {
                stk.push(new Frame(node.right, 0));
            }
        }
        return ans;
    }
}

/**
 * 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:
    const int inf = INT_MAX;
    int ans;
    int prev;

    int getMinimumDifference(TreeNode* root) {
        ans = inf, prev = inf;
        dfs(root);
        return ans;
    }

    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        ans = min(ans, abs(prev - root->val));
        prev = root->val;
        dfs(root->right);
    }
};


// Solution 2
/**
 * 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:
    int getMinimumDifference(TreeNode* root) {
        const int inf = 1 << 30;
        int ans = inf, pre = -inf;
        vector<pair<TreeNode*, int>> stk{{root, 0}};
        while (!stk.empty()) {
            auto [node, state] = stk.back();
            stk.pop_back();
            if (!node) {
                continue;
            }
            if (state == 0) {
                stk.emplace_back(node, 1);
                stk.emplace_back(node->left, 0);
                continue;
            }
            ans = min(ans, node->val - pre);
            pre = node->val;
            stk.emplace_back(node->right, 0);
        }
        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



# Solution 2
# 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: Optional[TreeNode]) -> int:
        pre = -inf
        ans = inf
        stk = [(root, 0)]
        while stk:
            node, state = stk.pop()
            if node is None:
                continue
            if state == 0:
                stk.append((node, 1))
                stk.append((node.left, 0))
                continue
            ans = min(ans, node.val - pre)
            pre = node.val
            stk.append((node.right, 0))
        return 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 abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}


// Solution 2
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
	const inf int = 1 << 30
	ans, pre := inf, -inf
	type frame struct {
		node  *TreeNode
		state int
	}
	stk := []frame{{root, 0}}
	for len(stk) > 0 {
		cur := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		node, state := cur.node, cur.state
		if node == nil {
			continue
		}
		if state == 0 {
			stk = append(stk, frame{node, 1}, frame{node.Left, 0})
			continue
		}
		ans = min(ans, node.Val-pre)
		pre = node.Val
		stk = append(stk, frame{node.Right, 0})
	}
	return ans
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    #[allow(dead_code)]
    pub fn get_minimum_difference(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut ret = i32::MAX;
        let mut prev = i32::MAX;
        Self::traverse(root, &mut prev, &mut ret);
        ret
    }

    #[allow(dead_code)]
    fn traverse(root: Option<Rc<RefCell<TreeNode>>>, prev: &mut i32, ans: &mut i32) {
        let left = root.as_ref().unwrap().borrow().left.clone();
        let right = root.as_ref().unwrap().borrow().right.clone();
        let val = root.as_ref().unwrap().borrow().val;
        if !left.is_none() {
            Self::traverse(left.clone(), prev, ans);
        }
        *ans = std::cmp::min(*ans, (*prev - val).abs());
        *prev = val;
        if !right.is_none() {
            Self::traverse(right.clone(), prev, ans);
        }
    }
}



// Solution 2
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn get_minimum_difference(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        const INF: i32 = 1 << 30;
        let mut ans = INF;
        let mut pre = -INF;
        let mut stk = vec![(root, 0)];
        while let Some((node, state)) = stk.pop() {
            if let Some(node) = node {
                if state == 0 {
                    let left = node.borrow().left.clone();
                    stk.push((Some(node), 1));
                    if left.is_some() {
                        stk.push((left, 0));
                    }
                } else {
                    let right = {
                        let b = node.borrow();
                        ans = ans.min(b.val - pre);
                        pre = b.val;
                        b.right.clone()
                    };
                    if right.is_some() {
                        stk.push((right, 0));
                    }
                }
            }
        }
        ans
    }
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function getMinimumDifference(root: TreeNode | null): number {
    if (!root) return 0;

    let prev = Number.MIN_SAFE_INTEGER;
    let min = Number.MAX_SAFE_INTEGER;

    const dfs = (node: TreeNode | null) => {
        if (!node) return;

        dfs(node.left);
        min = Math.min(min, node.val - prev);
        prev = node.val;
        dfs(node.right);
    };

    dfs(root);

    return min;
}



// Solution 2
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function getMinimumDifference(root: TreeNode | null): number {
    let ans = Infinity;
    let pre = -Infinity;
    const stk: [TreeNode | null, number][] = [[root, 0]];
    while (stk.length) {
        const [node, state] = stk.pop()!;
        if (!node) {
            continue;
        }
        if (state === 0) {
            stk.push([node, 1]);
            stk.push([node.left, 0]);
            continue;
        }
        ans = Math.min(ans, node.val - pre);
        pre = node.val;
        stk.push([node.right, 0]);
    }
    return ans;
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
    let [ans, pre] = [Infinity, -Infinity];
    const dfs = root => {
        if (!root) {
            return;
        }
        dfs(root.left);
        ans = Math.min(ans, root.val - pre);
        pre = root.val;
        dfs(root.right);
    };
    dfs(root);
    return ans;
};



// Solution 2
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
    let ans = Infinity;
    let pre = -Infinity;
    const stk = [[root, 0]];
    while (stk.length) {
        const [node, state] = stk.pop();
        if (!node) {
            continue;
        }
        if (state === 0) {
            stk.push([node, 1]);
            stk.push([node.left, 0]);
            continue;
        }
        ans = Math.min(ans, node.val - pre);
        pre = node.val;
        stk.push([node.right, 0]);
    }
    return ans;
};

530 - Minimum Absolute Difference in BST

530. Minimum Absolute Difference in BST

Description

Solutions

Solution 2: Explicit-Stack Inorder

All Problems

All Solutions

Welcome to Subscribe On Youtube

530. Minimum Absolute Difference in BST

Description

Solutions

Solution 2: Explicit-Stack Inorder

All Problems

All Solutions