Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
Problem:
https://www.geeksforgeeks.org/problems/bst-to-greater-sum-tree/1
BST to greater sum tree
Difficulty: Medium Accuracy: 66.73%
Given the root of a BST with unique node values, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
Examples:
Input: root = [11, 2, 29, 1, 7, 15, 40, N, N, N, N, N, N, 35, N]
Output: [119, 137, 75, 139, 130, 104, 0, N, N, N, N, N, N, 40, N]
Explanation: Every node is replaced with the sum of nodes greater than itself.
Input: root = [2, 1, 6, N, N, 3, 7]
Output: [16, 18, 7, N, N, 13, 0]
Explanation: Every node is replaced with the sum of nodes greater than itself.
Constraints :
1 ≤ node->data ≤ 3*104
1 ≤ number of nodes ≤ 3*104
Solution:
class Solution:
def transformTree(self, root):
self.sum = 0
def reverseInorder(node):
if not node:
return
reverseInorder(node.right)
self.sum += node.data
node.data = self.sum - node.data
reverseInorder(node.left)
reverseInorder(root)
return root
Top comments (0)