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:

 4
 / \
 2 6
 / \ 
1 3 

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)

Answer 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.

• curiousP: Couldn’t believe I made such a silly mistake. Thank you very much!
• curiousP: 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: 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.