Problem statement

https://leetcode.com/problems/split-bst/

Solution

The idea here is to use recursion: if we have V which is more or equal to our value of root, then left subtree is untouched and we need to recursively run function tor right subtree. Then we need to reattach new children: root.right = res[0]: new right children of root should be left answer for right subtree. Then we update res[0] = root and return res. Exactly the same logic we use if root.val > V.

Complexity

Time complexity is O(h), where h is height of tree, space we can say O(1), because we use existing nodes.

Code

class Solution:
    def splitBST(self, root, V):
        if not root: return [None, None]

        if root.val <= V:
            res = self.splitBST(root.right, V)
            root.right = res[0]
            res[0] = root
            return res
        else:
            res = self.splitBST(root.left, V)
            root.left = res[1]
            res[1] = root
            return res