Greater Than Tree
Solution to LeetCode Problem 538
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.
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.
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:
And that’s it. If you are familiar with binary search trees, this should be a fairly easy problem to solve. Thanks for reading!