Greater Than Tree

Solution to LeetCode Problem 538

Example of a Binary Search Tree


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.

Greater than tree conversion


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!



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store