Greater Than Tree
Solution to LeetCode Problem 538
Background
I recently interviewed for a junior developer position and wanted to share the solution to one of the interview problems I had. The problem is called Convert BST to Greater Tree, and it happens to be on LeetCode.
Intro
The basis of the problem is to take a binary search tree and convert it to another tree where the node values are equal to the sum of itself and all of the node values greater than itself.
Solution
The solution to this problem is actually pretty straightforward. We want to traverse our tree to the right, then add the value of the node to a sum variable, then return to the root node, and finally traverse left. It’s actually just reversed inorder traversal. Because we need to visit each node in the tree, the time complexity is O(N). I used a recursive approach to solve the problem, which is below:
https://gist.github.com/JulianAR97/ea4b9af127687e553315d9ed19fb13fb
And that’s it. If you are familiar with binary search trees, this should be a fairly easy problem to solve. Thanks for reading!
