Easy Leetcode: BST depth first search has stack overflow bug

Question

I'm working on a Leetcode problem, that can be found here: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

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

Example :

Input: root = [4,2,6,1,3,null,null] Output: 1 Explanation: Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note: I have implemented preorder traversal but my code ran into stack overflow bug, could someone help point out where the logic error is?

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDiffInBST(self, root):
        min_value = float('inf')

        def helper(node, min_value):
            print(node.val, "and", min_value)
            # if root is None
            if not root: 
                return None

            if node.left:
                min_value = min(min_value, node.val - node.left.val)
            if node.right:
                min_value = min(min_value, node.right.val - node.val)

            helper(root.left, min_value)
            helper(root.right, min_value)

            return min_value

        helper(root, min_value)

AFTER CHANGES:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDiffInBST(self, root):
        min_value = float('inf')

        def helper(node, min_value):
            # if root is None
            if not node: 
                return node
            print(node.val, min_value)

            if (node.left):
                min_value = min(min_value, node.val - node.left.val)
            if (node.right):
                min_value = min(min_value, node.right.val - node.val)

            helper(node.left, min_value)
            helper(node.right, min_value)

            return min_value

        helper(root, min_value)

user7217806 user7217806 · Accepted Answer · 2019-09-20T07:20:44

In your helper function you use root in the recursive call instead the current node. So instead iterating the whole tree, you continuously are calling the helper method for the same node, which is why the program gets stuck in an infinite recursion. It is very helpful to use a debugger for stepping through the code to investigate such issues.

Easy Leetcode: BST depth first search has stack overflow bug

1 Answers