We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Split BST

Number: 791

Difficulty: Medium

Paid? Yes

Companies: Google, Amazon, Coupang

Problem Description

Given the root of a Binary Search Tree (BST) and an integer target, split the tree into two subtrees such that:

  • The first subtree contains nodes with values smaller than or equal to target.
  • The second subtree contains nodes with values greater than target. It is important to note that the overall structure of the original tree should be preserved as much as possible, maintaining parent-child relations where both nodes fall into the same subtree.

Key Insights

  • Leverage the BST property: all nodes in the left subtree of a node are smaller than the node, and all nodes in the right subtree are larger.
  • Use recursion to navigate and split the tree based on the current node’s value compared to the target.
  • When a node’s value is less than or equal to target, its right subtree may contain nodes that belong to both split trees.
  • When a node’s value is greater than target, its left subtree may contain nodes that belong to both parts.
  • Carefully reconnect subtrees to maintain as much of the original structure as possible.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

Solution

The approach is to use recursion to split the BM tree. At each node:

  1. If the current node is null, return an array of two nulls.
  2. If the node’s value is less than or equal to the target:
    • Recursively split the right subtree.
    • Attach the left part of the split result as the new right child of the current node.
    • Return the current node as the root of the left subtree, and the right part as the root of the right subtree.
  3. Otherwise (node’s value is greater than target):
    • Recursively split the left subtree.
    • Attach the right part of the split result as the new left child of the current node.
    • Return the left part as the root of the left subtree, and the current node as the root of the right subtree. This recursion ensures that the BST property is maintained in both subtrees while preserving the structure where possible.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def splitBST(self, root: TreeNode, target: int) -> List[TreeNode]:
        # Base case: if the current node is None, return a pair of Nones.
        if not root:
            return [None, None]
        
        # If the current node's value is <= target:
        if root.val <= target:
            # Recursively split the right subtree.
            leftSubtree, rightSubtree = self.splitBST(root.right, target)
            # Link the left part to the current node's right.
            root.right = leftSubtree
            # current node becomes the root of the left subtree.
            return [root, rightSubtree]
        else:
            # Current node's value is > target, so split the left subtree.
            leftSubtree, rightSubtree = self.splitBST(root.left, target)
            # Link the right part to the current node's left.
            root.left = rightSubtree
            # current node becomes the root of the right subtree.
            return [leftSubtree, root]
← Back to All Questions