Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Minimum Difference Between BST Nodes

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 3 years ago

public class Solution {

    int result = Int32.MaxValue;
    int? prev =  null;
    public int GetMinimumDifference(TreeNode root) {
        DFS(root);
        return result;
    }

    private void DFS(TreeNode root)
    {
        if(root == null)
        return;

        DFS(root.left);
        if(prev.HasValue)
        result = Math.Min(result, root.val - prev.Value);
        prev = root.val;
        DFS(root.right);
    }
}
A

Anonymous

· 3 years ago

class Solution:
    def __init__(self):
        self.min_diff = float('inf')
        self.prev = None


    def minDiffInBST(self, root):
        if not root: 
            return self.min_diff

        self.minDiffInBST(root.left)

        if self.prev:
            node_diff = abs(root.val - self.prev.val)
            self.min_diff = min(self.min_diff, node_diff)
        
        self.prev = root
        
        self.minDiffInBST(root.right)

        return self.min_diff
A

Anonymous

· 3 years ago

public class Solution {
    public int minDiffInBST(TreeNode root) {
        int minDiff = Integer.MAX_VALUE;
        TreeNode prev = null;
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();

            if (prev != null) {
                minDiff = Math.min(curr.val - prev.val, minDiff);
            }
            
            prev = curr;
            
            curr = curr.right;
        }

        return minDiff;
    }
}
Show 1 reply

Reading Progress

0%

Vote for new content