<filename>week-4/solutions/structure.py<gh_stars>0
#Given a pre-order traversal history of a binary tree, check whether the path represents a valid BST or not. Return a string, either YES if the path can represent a valid BST, or NO if it cannot.
#
#Example 1:
#
#Input: "1 2 3 4 5 6 7"
#Output: "YES"
#Explanation: The path represents a valid BST.
#Example 2:
#
#Input: "1 2 3 4 5 6 7 8"
#Output: "YES"
#Explanation: The path represents a valid BST.
class BSTreeNode:
    def __init__(self, node_value):
        self.value = node_value
        self.left = self.right = None
    def insert(self, value):
        if self.left:
            self.insert()

def insert(node, data):
    if (data <= node.value):
        if node.left == None:
            node.left = BSTreeNode(data);
        else:
            node.left = insert(node.left, data)
        return node.left
    else:
        if node.right == None:
            node.right = BSTreeNode(data);
        else:
            node.right = insert(node.right, data)
        return node.right

def inorder(node):
    results = []
    if node.left:
        results.extend(inorder(node.left))
    results.append(node.value)
    if node.right:
        results.extend(inorder(node.right))
    return results

def build_tree(L):
    root = BSTreeNode(L.pop(0))
    new_node = insert(root, L.pop(0))
    while L:
        new_node = insert(new_node, L.pop(0))
    return root

L = [2,1,3,4,5]
L = [2,1,3]
#L_copy =[*L]
#root = build_tree(L)
#results = (inorder(root))
#L_copy.sort()
def is_bst(L):
    root = float('-inf')
    stack = []
    for i in range(len(L)):
        if L[i] < root:
            return 'NO'
        while len(stack) != 0 and L[i] > stack[-1]:
            root = stack.pop()
        stack.append(L[i])
    return 'YES'

print(is_bst(L))
<filename>week-4/solutions/structure.py<gh_stars>0
#Given a pre-order traversal history of a binary tree, check whether the path represents a valid BST or not. Return a string, either YES if the path can represent a valid BST, or NO if it cannot.
#
#Example 1:
#
#Input: "1 2 3 4 5 6 7"
#Output: "YES"
#Explanation: The path represents a valid BST.
#Example 2:
#
#Input: "1 2 3 4 5 6 7 8"
#Output: "YES"
#Explanation: The path represents a valid BST.
class BSTreeNode:
    def __init__(self, node_value):
        self.value = node_value
        self.left = self.right = None
    def insert(self, value):
        if self.left:
            self.insert()

def insert(node, data):
    if (data <= node.value):
        if node.left == None:
            node.left = BSTreeNode(data);
        else:
            node.left = insert(node.left, data)
        return node.left
    else:
        if node.right == None:
            node.right = BSTreeNode(data);
        else:
            node.right = insert(node.right, data)
        return node.right

def inorder(node):
    results = []
    if node.left:
        results.extend(inorder(node.left))
    results.append(node.value)
    if node.right:
        results.extend(inorder(node.right))
    return results

def build_tree(L):
    root = BSTreeNode(L.pop(0))
    new_node = insert(root, L.pop(0))
    while L:
        new_node = insert(new_node, L.pop(0))
    return root

L = [2,1,3,4,5]
L = [2,1,3]
#L_copy =[*L]
#root = build_tree(L)
#results = (inorder(root))
#L_copy.sort()
def is_bst(L):
    root = float('-inf')
    stack = []
    for i in range(len(L)):
        if L[i] < root:
            return 'NO'
        while len(stack) != 0 and L[i] > stack[-1]:
            root = stack.pop()
        stack.append(L[i])
    return 'YES'

print(is_bst(L))
#Given a pre-order traversal history of a binary tree, check whether the path represents a valid BST or not. Return a string, either YES if the path can represent a valid BST, or NO if it cannot. # #Example 1: # #Input: "1 2 3 4 5 6 7" #Output: "YES" #Explanation: The path represents a valid BST. #Example 2: # #Input: "1 2 3 4 5 6 7 8" #Output: "YES" #Explanation: The path represents a valid BST. #L_copy =[*L] #root = build_tree(L) #results = (inorder(root)) #L_copy.sort()