Greater Than Tree

Julian Rosenthal
2 min readJun 8, 2021

--

Solution to LeetCode Problem 538

Example of a Binary Search Tree

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.

Greater than tree conversion

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!

--

--

No responses yet