LeetCode 776: Split BST Solution

Master LeetCode problem 776 (Split BST), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

776. Split BST

Medium

Tree Binary Search Tree Recursion Binary Tree

Problem Explanation

Explanation

The problem asks us to split a given binary search tree (BST) into two separate BSTs based on a target value V. The goal is to create two trees: one containing all nodes with values less than or equal to V and the other containing all nodes with values greater than V.

To solve this problem, we can recursively split the original tree into two parts by traversing it. We need to consider the following cases:

If the current node's value is less than or equal to V, it will be part of the left subtree. In this case, we can recursively split the right subtree of the current node.
If the current node's value is greater than V, it will be part of the right subtree. In this case, we can recursively split the left subtree of the current node.

We will keep track of the root nodes of the resulting left and right subtrees and connect them accordingly.

Solution Code

class Solution {
    public TreeNode[] splitBST(TreeNode root, int V) {
        if (root == null) {
            return new TreeNode[]{null, null};
        } else if (root.val <= V) {
            TreeNode[] split = splitBST(root.right, V);
            root.right = split[0];
            return new TreeNode[]{root, split[1]};
        } else {
            TreeNode[] split = splitBST(root.left, V);
            root.left = split[1];
            return new TreeNode[]{split[0], root};
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 776 (Split BST)?

This page provides optimized solutions for LeetCode problem 776 (Split BST) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 776 (Split BST)?

The time complexity for LeetCode 776 (Split BST) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 776 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 776 in Java, C++, or Python.

Back to LeetCode Solutions