Skip to Content

Convert BST to Greater Tree

Home | Coding Interviews | Simple Data Structures | Convert BST to Greater Tree

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

def convertBST(self, root):
    def visit1(root):
        if root:
            visit1(root.left)
            vals.append(root.val)
            visit1(root.right)
    vals = []
    visit1(root)
    
    self.s = 0
    def visit2(root):
        if root:
            visit2(root.right)
            self.s += vals.pop()
            root.val = self.s
            visit2(root.left)
    visit2(root)

    return root

Posted by Jamie Meyer 7 months ago

Related Problems

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Given a binary tree, determine if it is height-balanced.

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.