I am trying to understand the recursive call within the binary function is_bst. The goal of the function is to check if a tree is a binary search tree or not. Note, This is just an excerpt from the complete function. I am trying to understand what is happening on this block of code is_bst_l, min_l, max_l = is_bst(node.left) in the is_bst function. The is_bst function return (True, None, None), I am trying to figure out how the function came up with the return value by going through the function recursively. The is_bst function takes as input the binary tree node from the parse_tuple function. As an example, when I try to unpack this line of code is_bst_l, min_l, max_l = node.left outside the is_bst function I get TypeError: cannot unpack non-iterable TreeNode object, but within the function, I don't get an error. My Question is

1. what is happening recursively within the is_bst function.
2. How can I don't get the unpack TypeError within the is_bst function.

`

#Tree Class
class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

#function converts a turble to a binary tree
 def parse_tuple(data):
    # print(data)
    if isinstance(data, tuple) and len(data) == 3:
        node = TreeNode(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    elif data is None:
        node = None
    else:
        node = TreeNode(data)
    return node

Function Checks if a tree is a Binary search tree or not.

def remove_none(nums):
return [x for x in nums if x is not None]

def is_bst(node):
    if node is None:
        return True, None, None
    
    is_bst_l, min_l, max_l = is_bst(node.left)
    is_bst_r, min_r, max_r = is_bst(node.right)
    is_bst_node = (is_bst_l and is_bst_r and 
              (max_l is None or node.key > max_l) and 
              (min_r is None or node.key < min_r))
#     print('Minkey left: ', min_l, 'Nodekey :', node.key, 'Maxkey left: ',min_r)
#     print('Minkey left: ', max_l, 'Nodekey :', node.key, 'Maxkey left: ',max_r)
    min_key = min(remove_none([min_l, node.key, min_r]))
    max_key = max(remove_none([max_l, node.key, max_r]))
    
    # print(node.key, min_key, max_key, is_bst_node)
        
    return is_bst_node, min_key, max_key

#function call

my_tuple= ((None,3,None),2,(None,5,None))
node = parse_tuple(my_tuple)

CodePudding user response：

A tree is a BST if recursively for every node:

• Its left tree if it exists is a BST
• Its right tree if it exists is a BST
• The largest value of the left tree, if it exists, must be smaller than the node's value
• The smallest value of the right tree, if it exists, must be larger than the node's value

Hence it makes sense for the return value to the the tuple of three values:

• Am I a BST?
• What is the smallest node in my subtree
• What is the largest node in my subtree.

CodePudding user response：

The function is returning the maximum and minimum key on the left and right of the current node (in addition to the True/False result of the check). Its recursion assembles these keys / validity states from the left and right nodes creating the need to manage (i.e. exclude) None results from the subnodes returned value.

This is overly complex, and probably not worth your time to analyze and understand.

I think you'll find this one a bit more straightforward:

def is_bst(node,minKey=None,maxKey=None):
    if node is None: return True
    if minKey is not None and node.key<=minKey: return False
    if maxKey is not None and node.key>=maxKey: return False
    if not is_bst(node.left,minKey,self.key):   return False
    if not is_bst(node.right,self.key,maxKey):  return False
    return True