Convert BST to Greater Tree – Python 3 (Week 4 – 04)

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

class Solution:
    """
    @param root: the root of binary tree
    @return: the new root
    """
    def convertBST(self, root):
        # write your code here
        self.sum = 0
        self.dfs(root)
        
        return root
    
        
    def dfs(self, root):
        if not root:
            return
        self.dfs(root.right)
        self.sum += root.val
        root.val = self.sum
        self.dfs(root.left)
        

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.total = 0
    
    def convertBST(self, root: TreeNode) -> TreeNode:
        
       #Recurision
        if root is not None:
            self.convertBST(root.right)
            self.total += root.val
            root.val = self.total
            self.convertBST(root.left)
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
  
    def convertBST(self, root: TreeNode) -> TreeNode:
        
        #Iteration
        total = 0
        stack = []
        node = root
        
        while node or stack: #"while stack or node is not None" "while stack or node"
            #"while node or stack is not None" is wrong****
            
            while node is not None:
                stack.append(node)
                node = node.right #add all node to the stack until none
                
            node = stack.pop()
            total += node.val
            node.val = total
            
            node = node.left
            
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
  
    def convertBST(self, root: TreeNode) -> TreeNode:
        
        node, total = root, 0
        while node:
            if not node.right:
                total += node.val
                node.val = total
                node = node.left
            else:
                pred = node.right
                while pred.left and pred.left is not node:
                    pred = pred.left
                if pred.left is node:
                    pred.left = None
                    total += node.val
                    node.val = total
                    node = node.left
                else:
                    pred.left = node
                    node = node.right
        return root