Leetcode Day 18 - Binary Search Tree: Transformations and Conversions

Binary Tree

Link to note about binary tree

Diff	Problem	Python	Java
	669 Trim a Binary Search Tree	✅
	108 Convert Sorted Array to Binary Search Tree	✅
	538 Convert BST to Greater Tree	✅

Trim a Binary Search Tree

Link to Leetcode question¹

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

Solution

A detailed explaination of solution can be found here².

Python

class Solution(object):
    def trimBST(self, root, low, high):
        if root is None:
            return None

        root.left = self.trimBST(root.left, low, high) 
        root.right = self.trimBST(root.right, low, high)
        
        if root.val < low:
            root = root.right
        elif root.val > high:
            root = root.left
        
        return root

Convert Sorted Array to Binary Search Tree

Link to Leetcode question³

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Solution

A detailed explaination of solution can be found here⁴.

Python

class Solution(object):
    def sortedArrayToBST(self, nums):
        if len(nums) == 0:
            return None    
        if len(nums) == 1:
            return TreeNode(nums[0])
        
        i = len(nums) // 2
        node = TreeNode(nums[i])
        node.left = self.sortedArrayToBST(nums[:i])
        if i + 1 < len(nums):
            node.right = self.sortedArrayToBST(nums[i+1:])
        
        return node

Similar Questions

Diff	Similar Questions	Python	Java
	109 Convert Sorted List to Binary Search Tree5

Convert BST to Greater Tree

Link to Leetcode question⁶

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.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2

Input: root = [0,null,1]
Output: [1,null,1]

Solution

A detailed explaination of solution can be found here⁷.

Python

class Solution(object):
    def convertBST(self, root):
        
        def getSum(node, s):
            if node is None:
                return 0

            new_s = s + node.val
            new_s += getSum(node.right,s)
            node.val = new_s
            new_s += getSum(node.left,new_s)

            return new_s - s
        
        getSum(root, 0)
        return root

Reference

1. Leetcode-669 Trim a Binary Search Tree: https://leetcode.com/problems/trim-a-binary-search-tree/description/. ↩︎

2. 代码随想录-修剪二叉搜索树: https://programmercarl.com/0669.修剪二叉搜索树.html. ↩︎

3. Leetcode-108 Convert Sorted Array to Binary Search Tree: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/ ↩︎

4. 代码随想录-将有序数组转换为二叉搜索树: https://programmercarl.com/0108.将有序数组转换为二叉搜索树.html. ↩︎

5. Leetcode-109. Convert Sorted List to Binary Search Tree: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/. ↩︎

6. Leetcode-538 Convert BST to Greater Tree: https://leetcode.com/problems/convert-bst-to-greater-tree/description/. ↩︎

7. 代码随想录-把二叉搜索树转换为累加树: https://programmercarl.com/0538.把二叉搜索树转换为累加树.html. ↩︎