Devin's Blog

Minimum Distance Between BST Nodes

2 min read

TARGET DECK: Leetcode FILE TAGS: Easy

Intuition

  • If not using a list, toss elements into an array and then find the minimum difference between each adjacent element.
  • This works since Binary Tree Inorder Traversal is used, and since we have a Binary Search Tree, this tree preserves the property that an Inorder traversal keeps ascending order.
  • When doing without a list, notice the following observation:
    • Via inorder traversal, when I go down the left side of my tree, if I store that as my previous value, then I know my current node is greater than it (hence node.val - leftNode.val).
    • On the other hand, if I am in the node to my right, I know the node to my right is greater than the node I came from, and so if I set prevVal = node.val, this becomes rightNode.val - node.val.
    • Likewise, when I return, I am saving as prevVal the node.right.val, and that node is the closest to the root node, so that comparison is also accounted for.

Complexity

Runtime

due to traversal of all nodes.

Space

  • if storing a list,
  • otherwise due to the stack trace, or O(1) if not considering this.
    • If you are on a balanced binary search tree, then at each level, there are 2, 4, 8, … = n elements, so .

Code

Without List

# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
        prevVal = -1
        minDiff = inf
 
        def inorder(node):
            nonlocal prevVal
            nonlocal minDiff
 
            if not node:
                return
 
            inorder(node.left)
 
            if prevVal != -1:
                minDiff = min(minDiff, node.val - prevVal)
            prevVal = node.val
 
            inorder(node.right)
 
        inorder(root)
        return minDiff

Via List

# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
        ordered = []
        def r(node):
            if not node:
                return None
            r(node.left)
            ordered.append(node.val)
            r(node.right)
 
        r(root)
        minDiff = inf
        for i in range(len(ordered) - 1):
            minDiff = min(minDiff, ordered[i + 1] - ordered[i])
        return minDiff

Notes

Cards

START Basic Front: Minimum Distance Between Bst Nodes Back: Store the previous node and do Binary Tree Inorder Traversal.

END

References

Graph View