1038. Binary Search Tree to Greater Sum Tree || LeetCode POTD || Explained in HINDI

Instagram link:- / reelcoding
/ @reelcoding
Approach 1:-
Initialization:
We initialize a global variable globalSum to keep track of the cumulative sum of node values as we traverse the tree.
Recursive Function:
We define a recursive function solve(TreeNode node) that processes each node of the tree. The recursion follows a reverse in-order traversal (right, root, left).
Processing Nodes:
For each node, we first traverse the right subtree.
We then update globalSum by adding the current node's value.
The current node's value is updated to globalSum.
Finally, we traverse the left subtree.
Main Function:
In the main function bstToGst(TreeNode root), we initialize globalSum to 0.
We call the solve function starting from the root node.
We return the modified root node.
Time and Space Complexity
Time Complexity: O(n)
We traverse each node exactly once in the tree, where n is the number of nodes.
Space Complexity: O(h)
The space complexity is determined by the height of the tree h, which corresponds to the recursion stack space.
Approach 2 :-
Initialization:
We initialize a globalSum variable to keep track of the cumulative sum of node values as we traverse the tree.
Iterative In-Order Traversal:
We use a stack to perform a reverse in-order traversal (right, root, left).
We start with the root node and push all the right children onto the stack until we reach a null node.
Processing Nodes:
We pop the node from the stack and update globalSum by adding the current node's value.
We update the current node's value to globalSum.
We then move to the left child of the popped node and repeat the process until the stack is empty and there are no more nodes to process.
Time and Space Complexity
Time Complexity: O(n)
We visit each node exactly once in the tree, where n is the number of nodes.
Space Complexity: O(h)
The space complexity is determined by the height of the tree h, corresponding to the stack space used during traversal.
Approach 3:-
Initialization:
We initialize a globalSum variable to keep track of the cumulative sum of node values as we traverse the tree.
Morris Traversal:
The Morris traversal is a tree traversal algorithm that allows us to traverse the tree without using extra space for a stack or recursion.
We start at the root node and use the right subtree to create a temporary threaded binary tree, facilitating reverse in-order traversal.
Threaded Binary Tree:
For each node, if it has a right child, we find the "post extreme left" node in the right subtree.
If the left link of the "post extreme left" node is null, we create a temporary link back to the current node and move to the right child.
If the left link of the "post extreme left" node is not null, we remove the temporary link, update the globalSum, update the current node’s value, and move to the left child.
Time and Space Complexity
Time Complexity: O(n)
We visit each node exactly twice in the tree, once when creating the threaded binary tree and once when reverting the changes, where
n is the number of nodes.
Space Complexity: O(1)
Morris traversal uses no extra space for stack or recursion, making it an in-place algorithm.
Whether you're new to problem-solving or seeking insights into Java programming techniques, this video offers valuable insights into tackling similar challenges effectively.
Do join with me guys for daily problem solving on LeetCode.
Please like and subscribe this channel and share among your friends, it helps me to motivate and bring more videos for you guys. ❤️❤️
Soon, DSA batch (Hinglish) is going to launch on this channel. So, do subscribe so that you will get the notification for all new videos.👍👍🔔🔔.
Do comment if any doubts left. Thank you 😊
#leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa
#CodingExplanation #AlgorithmTutorial #JavaProgramming #DataStructures #DynamicProgramming #CodeExplanation #ProgrammingTutorial #AlgorithmExplanation #TechTutorial #LearnToCode #ProblemSolving #ProgrammingConcepts #SoftwareDevelopment #TechEducation #CodingCommunity #CodeBreakdown #ComputerScience
#JavaTutorial #AlgorithmAnalysis #EducationalContent
1038. Binary Search Tree to Greater Sum Tree
Leetcode 1038
Binary Search Tree to Greater Sum Tree
Leetcode daily challenge
Leetcode potd
1038 Binary Search Tree to Greater Sum Tree
leetcode potd today solution
leetcode potd today
leetcode grind
leetcode questions for interview
leetcode series
leetcode hindi

[@SupriyaDesai101]

Nicely explained! ❤❤❤

[@reelcoding]

Code link :- leetcode.com/problems/binary-search-tree-to-greater-sum-tree/solutions/5366697/java-solution-explained-in-hindi-3-approaches/