Skip to content

776. Split BST 👍

  • Time: $O(h)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  vector<TreeNode*> splitBST(TreeNode* root, int target) {
    if (root == nullptr)
      return {nullptr, nullptr};
    if (root->val > target) {
      const vector<TreeNode*> res = splitBST(root->left, target);
      root->left = res[1];
      return {res[0], root};
    } else {  // root->val <= target
      const vector<TreeNode*> res = splitBST(root->right, target);
      root->right = res[0];
      return {root, res[1]};
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public TreeNode[] splitBST(TreeNode root, int target) {
    if (root == null)
      return new TreeNode[] {null, null};
    if (root.val > target) {
      TreeNode[] res = splitBST(root.left, target);
      root.left = res[1];
      return new TreeNode[] {res[0], root};
    } else { // root.val <= target
      TreeNode[] res = splitBST(root.right, target);
      root.right = res[0];
      return new TreeNode[] {root, res[1]};
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def splitBST(self, root: TreeNode | None, target: int) -> list[TreeNode | None]:
    if not root:
      return None, None
    if root.val > target:
      left, right = self.splitBST(root.left, target)
      root.left = right
      return left, root
    else:  # root.val <= target
      left, right = self.splitBST(root.right, target)
      root.right = left
      return root, right