Solution 1 - Inorder Traversal (Recursive)

Perform an inorder traversal of the BST, which visits nodes in sorted order. Track the previous node's value and compute the difference at each step, keeping the minimum.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0530.1 - Solution 1 - Recursive Inorder Traversal """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
import math

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        """Get Minimum Difference Function"""
        self.prev = None
        self.min_diff = math.inf

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            if self.prev is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev)
            self.prev = node.val
            inorder(node.right)

        inorder(root)
        return self.min_diff


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Tree: [4, 2, 6, 1, 3]
    root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
    print(Solution().getMinimumDifference(root))  # Output: 1

    # Tree: [1, 0, 48, None, None, 12, 49]
    root2 = TreeNode(1, TreeNode(0), TreeNode(48, TreeNode(12), TreeNode(49)))
    print(Solution().getMinimumDifference(root2))  # Output: 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0530 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(r){let st=[],p=null,b=Infinity,c=r;while(c||st.length){while(c){st.push(c);c=c.l}c=st.pop();if(p!==null)b=Math.min(b,c.v-p);p=c.v;c=c.r}return b}
console.log(solve({v:4,l:{v:2,l:{v:1},r:{v:3}},r:{v:6}}));

/** 0530 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(r){let st=[],p=null,b=Infinity,c=r;while(c||st.length){while(c){st.push(c);c=c.l}c=st.pop();if(p!==null)b=Math.min(b,c.v-p);p=c.v;c=c.r}return b}
console.log(solve({v:4,l:{v:2,l:{v:1},r:{v:3}},r:{v:6}}));

// 0530 - Runnable implementation

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import ("fmt";"sort";"strings")

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
type N struct{v int;l,r *N}
func solve(r *N)int{st:=[]*N{};p,b:=0,int(^uint(0)>>1);has:=false;for r!=nil||len(st)>0{for r!=nil{st=append(st,r);r=r.l};r=st[len(st)-1];st=st[:len(st)-1];if has&&r.v-p<b{b=r.v-p};p=r.v;has=true;r=r.r};return b}
func main(){fmt.Println(solve(&N{4,&N{2,&N{1,nil,nil},&N{3,nil,nil}},&N{6,nil,nil}}))}

// 0530 - Runnable implementation

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
fn solve(mut a:Vec<i32>)->i32{a.sort();a.windows(2).map(|w|w[1]-w[0]).min().unwrap()}fn main(){println!("{}",solve(vec![4,2,6,1,3]));}

Solution 2 - Inorder Traversal (Iterative)

Same inorder approach but using an explicit stack instead of recursion. This avoids potential stack overflow for very deep trees.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0530.2 - Solution 2 - Iterative Inorder Traversal """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
import math

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        """Get Minimum Difference Function"""
        stack = []
        prev = None
        min_diff = math.inf
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            if prev is not None:
                min_diff = min(min_diff, curr.val - prev)
            prev = curr.val
            curr = curr.right

        return min_diff


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Tree: [4, 2, 6, 1, 3]
    root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
    print(Solution().getMinimumDifference(root))  # Output: 1

    # Tree: [1, 0, 48, None, None, 12, 49]
    root2 = TreeNode(1, TreeNode(0), TreeNode(48, TreeNode(12), TreeNode(49)))
    print(Solution().getMinimumDifference(root2))  # Output: 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0530 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(r){let st=[],p=null,b=Infinity,c=r;while(c||st.length){while(c){st.push(c);c=c.l}c=st.pop();if(p!==null)b=Math.min(b,c.v-p);p=c.v;c=c.r}return b}
console.log(solve({v:4,l:{v:2,l:{v:1},r:{v:3}},r:{v:6}}));

/** 0530 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(r){let st=[],p=null,b=Infinity,c=r;while(c||st.length){while(c){st.push(c);c=c.l}c=st.pop();if(p!==null)b=Math.min(b,c.v-p);p=c.v;c=c.r}return b}
console.log(solve({v:4,l:{v:2,l:{v:1},r:{v:3}},r:{v:6}}));

// 0530 - Runnable implementation

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import ("fmt";"sort";"strings")

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
type N struct{v int;l,r *N}
func solve(r *N)int{st:=[]*N{};p,b:=0,int(^uint(0)>>1);has:=false;for r!=nil||len(st)>0{for r!=nil{st=append(st,r);r=r.l};r=st[len(st)-1];st=st[:len(st)-1];if has&&r.v-p<b{b=r.v-p};p=r.v;has=true;r=r.r};return b}
func main(){fmt.Println(solve(&N{4,&N{2,&N{1,nil,nil},&N{3,nil,nil}},&N{6,nil,nil}}))}

// 0530 - Runnable implementation

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
fn solve(mut a:Vec<i32>)->i32{a.sort();a.windows(2).map(|w|w[1]-w[0]).min().unwrap()}fn main(){println!("{}",solve(vec![4,2,6,1,3]));}

Solution 3 - Inorder to Sorted List

Collect all node values via inorder traversal into a sorted list, then iterate through adjacent pairs to find the minimum difference.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0530.3 - Solution 3 - Inorder to Sorted List """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional, List
import math

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        """Get Minimum Difference Function"""
        values: List[int] = []

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

        inorder(root)

        min_diff = math.inf
        for i in range(1, len(values)):
            min_diff = min(min_diff, values[i] - values[i - 1])

        return min_diff


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Tree: [4, 2, 6, 1, 3]
    root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
    print(Solution().getMinimumDifference(root))  # Output: 1

    # Tree: [1, 0, 48, None, None, 12, 49]
    root2 = TreeNode(1, TreeNode(0), TreeNode(48, TreeNode(12), TreeNode(49)))
    print(Solution().getMinimumDifference(root2))  # Output: 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0530 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(r){let st=[],p=null,b=Infinity,c=r;while(c||st.length){while(c){st.push(c);c=c.l}c=st.pop();if(p!==null)b=Math.min(b,c.v-p);p=c.v;c=c.r}return b}
console.log(solve({v:4,l:{v:2,l:{v:1},r:{v:3}},r:{v:6}}));

/** 0530 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(r){let st=[],p=null,b=Infinity,c=r;while(c||st.length){while(c){st.push(c);c=c.l}c=st.pop();if(p!==null)b=Math.min(b,c.v-p);p=c.v;c=c.r}return b}
console.log(solve({v:4,l:{v:2,l:{v:1},r:{v:3}},r:{v:6}}));

// 0530 - Runnable implementation

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import ("fmt";"sort";"strings")

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
type N struct{v int;l,r *N}
func solve(r *N)int{st:=[]*N{};p,b:=0,int(^uint(0)>>1);has:=false;for r!=nil||len(st)>0{for r!=nil{st=append(st,r);r=r.l};r=st[len(st)-1];st=st[:len(st)-1];if has&&r.v-p<b{b=r.v-p};p=r.v;has=true;r=r.r};return b}
func main(){fmt.Println(solve(&N{4,&N{2,&N{1,nil,nil},&N{3,nil,nil}},&N{6,nil,nil}}))}

// 0530 - Runnable implementation

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
fn solve(mut a:Vec<i32>)->i32{a.sort();a.windows(2).map(|w|w[1]-w[0]).min().unwrap()}fn main(){println!("{}",solve(vec![4,2,6,1,3]));}

0530 - Minimum Absolute Difference in BST

Solution 1 - Inorder Traversal (Recursive)

Solution 2 - Inorder Traversal (Iterative)

Solution 3 - Inorder to Sorted List