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 · Accepted Answer · 2019-09-20 07:20:44Z

1

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.

answered Sep 20, 2019 at 7:20

user7217806

2,1192 gold badges12 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

curiousP Over a year ago

Couldn’t believe I made such a silly mistake. Thank you very much!

curiousP Over a year ago

Thank you for helping, but could you please help look at my updated code. It stops running into the stack overflow bug, but returns a None value for min_value even when I print out the min_value, it looks correct for every nodes.

user7217806 Over a year ago

You are welcome! As for your update: you are missing a return statement in your minDiffInBST, so it does not return any value, therefore resulting in None.

Collectives™ on Stack Overflow

Easy Leetcode: BST depth first search has stack overflow bug

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related