Ggthjy

import sys





class Node:

    def __init__(self, value):

        self.left = None

        self.right = None

        self.value = value



    def __str__(self):

        return f"{self.value} "





class Sum:

    def __init__(self, val):

        self.s = val



    def getS(self):

        return self.s



    def update(self, val):

        self.s += val





class BST:

    def __init__(self):

        self.root = None



    def insert(self, key):

        curr = self.root

        parent = None

        if self.root:

            while curr and curr.value != key:

                parent = curr

                if curr.value < key:

                    curr = curr.right

                else:

                    curr = curr.left

        else:

            self.root = Node(key)

            return



        if parent:

            if parent.value < key:

                parent.right = Node(key)

            else:

                parent.left = Node(key)



    def delete(self, key):

        pass



    def _doFind(self, root, key):

        if root:

            if root.value == key:

                return root

            if root.value < key:

                self._doFind(root.right, key)

            else:

                self._doFind(root.left, key)



    def find(self, key):

        self._doFind(self.root, key)



    def _inorder(self, root):

        if root:

            self._inorder(root.left)

            print(root, " ")

            self._inorder(root.right)



    def inorder(self):

        self._inorder(self.root)



    def _preorder(self, root):

        if root:

            print(root, " ")

            self._preorder(root.left)

            self._preorder(root.right)



    def preorder(self):

        self._preorder(self.root)



    def _postorder(self, root):

        if root:

            self._postorder(root.left)

            self._postorder(root.right)

            print(root, " ")



    def postorder(self):

        self._postorder(self.root)



    def sumRToL(self, root, s):

        if root:

            self.sumRToL(root.right, s)

            s.update(root.value)

            root.value = s.getS()

            self.sumRToL(root.left, s)



    def sumelementsfromRtoLinplace(self):

        s = Sum(0)

        self.sumRToL(self.root, s)



    def validate(self, root, low, high):

        # Look for iterative solutions as well, probably using some stack

        return (not root) or (low <= root.value <= high and (

                self.validate(root.left, low, root.value) and self.validate(root.right, root.value, high)))



    def validatebst(self):

        max = sys.maxsize

        min = -sys.maxsize - 1

        return self.validate(self.root, min, max)



    def isSameTree(self, p, q):

        # Task : Can a level order solve this. Any non-recursive solutions as stack depth is not reliable?

        """

         Checks the value as well as topological order

        :type p: Node

        :type q: Node

        :rtype: bool

        """

        if not p and not q:

            return True

        elif p and q and p.value == q.value:

            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

        return False





def test_main():

    bst = BST()

    bst.insert(1)

    bst.insert(2)

    bst.insert(3)

    bst.insert(4)

    bst.insert(5)

    # bst.root.left = Node(34) # Mess up the tree

    # bst.insert(2)

    # bst.insert(3)

    # bst.insert(4)

    # bst.insert(5)

    # bst.sumelementsfromRtoLinplace()

    # bst.inorder()

    bst1 = BST()

    bst1.insert(1)

    bst1.insert(2)

    bst1.insert(3)

    bst1.insert(4)

    bst1.insert(5)



    print('Same tree : ', bst.isSameTree(bst.root, bst1.root))

    print("Valid Tree : ", bst.validatebst())





if __name__ == '__main__':

    test_main()

P.S : I had to create the Sum class as there's no way to share the same primitive int across stack calls as there is no pass by reference in Python. I wanted to avoid using global variables throughout.