Demo entry 6660855

test

   

Submitted by anonymous on Nov 16, 2017 at 19:59
Language: Python 3. Code size: 2.8 kB.

class TreeNode:
      def __init__(self,val):
            self.left = None
            self.right = None
            self.val = val

class BST:
      def __init__(self):
            self.root = None
            self.tsize = 0
            self.small = -1
            self.large = -1
            self.sum = 0
      def insert(self,val):
            
            self.insertnode(self.root,val)

      def insertnode(self,root,val):
          if root is None:
              self.root = TreeNode(val)
              self.tsize = self.tsize + 1
          else:
              
              if root.val < val:
                  if root.right is None:
                      root.right = TreeNode(val)
                      self.tsize = self.tsize + 1
                  else:
                      self.insertnode(root.right, val)
              else:
                  if root.left is None:
                      root.left = TreeNode(val)
                      self.tsize = self.tsize + 1
                  else:
                      self.insertnode(root.left, val)
                      
      def printTree(self):
            self.inorder(self.root)

      def inorder(self,root):
            if root:
                  self.inorder(root.left)
                  print(root.val)
                  self.inorder(root.right)
                  
      def size(self):
            return self.tsize

      def smallest(self):
            self.find_left(self.root)
            return self.small
            
      def find_left(self,root):
            if not root.left:
                  self.small = root.val
            else:                 
                  self.find_left(root.left)
                  
      def largest(self):
            self.find_right(self.root)
            return self.large
            
      def find_right(self,root):
            if not root.right:
                  self.large = root.val
            else:                 
                  self.find_right(root.right)

      def greaterSumTree(self):

            if self.root:
                  self.traversal(self.root)     
            return self.root
        
      def traversal(self,root):
            #inroder: so 1.go left, 2. visit, 3. go right
            #we need to use resverse-inorder here, so ,321
            if root.right:
                  self.traversal(root.right)
                  
            temp =  root.val 
            root.val = self.sum
            self.sum = self.sum + temp
        
            if root.left:
                  self.traversal(root.left)

bst = BST()
array =  [5, 3, 9, 7, 1, 4, 0, 12, 11, 13, 15, 6, 2, 8, 10, 14]
for item in array:
    bst.insert(item)
bst.printTree()
#print(bst.size())
#print(bst.smallest())
#print(bst.largest())
print(bst.greaterSumTree())
bst.printTree()

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).