Add all greater values to every node in a given BST
Given a Binary Search Tree (BST), modify it so that all greater values in the given BST are added to every node
class TreeNode(object):
def __init__(self,val):
self.value = val
self.left = None
self.right = None
def __repr__(self):
return str(self.value)
class Solution(object):
def add_larger_values(self,root):
self.sum = 0
self._add_larger_values(root)
def _add_larger_values(self,root):
if not root:
return
self._add_larger_values(root.right)
temp = root.value
root.value += self.sum
self.sum +=temp
self._add_larger_values(root.left)
Observation:
It is similar to inorder traversal, as in inorder traversal u call print statement only once , so is in this case added root value to sum should be done only once