# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Setup

import time
import math
import matplotlib.pyplot as plt
import numpy as np
import random as rnd
np.random.seed(123)
rnd.seed(123)

# # Trees and Hash Tables: Theory
# - Trees
# - Hash Tables

# ## Base Algorithms
# - Binary Search Tree 
#     - search
#     - add
#     - remove
#     - traverse: BFS
#     - traverse: DFS (preorder, inorder, postorder)
#     - predecessor, successor
#     - reconstruct BST
#     
# - Hash tables
#     - search
#     - add
#     - remove



# # Sample Problems and Solutions

# ## Largest BST
# ### Description
# Given a tree, find largest Binary Search Tree among all possible subtrees

# ### Solution

# +
# Assume:
# class Node():
#    def __init__(self, v=None, l=None, r=None):
#        self.v = val
#        self.l = l
#        self.r = r

# complete the function below

def find_largest_bst(root):
    if root == None:
        return 0
        
    def _helper(node):
        # base
        if node.l == None and node.r == None:
            return 1, True, node.v, node.v
        
        # recursive part
        
        ## check children
        if node.l != None:
            lval, lbst, llo, lhi = _helper(node.l)
        else:
            lval, lbst, llo, lhi = 0, True, node.v, node.v
        if node.r != None:
            rval, rbst, rlo, rhi = _helper(node.r)
        else:
            rval, rbst, rlo, rhi = 0, True, node.v, node.v
            
        ## combine results
        if lhi <= node.v and node.v <= rlo and lbst and rbst:
            return 1 + lval + rval, True, llo, rhi
        else:
            return max(lval, rval), False, llo, rhi

        
    val, bst, lo, hi = _helper(root)
    return val

StarcoderdataJupyterScriptsDedupFiltered