18 Split BST

Problem Statement

Write a Recursive Approach to Split BST.

Given the root of a Binary Search Tree (BST) and an integer target, split the tree into two separate subtrees based on this target value.

• The first subtree should contain all nodes with values less than or equal to the target.
• The second subtree should contain all nodes with values greater than the target.

Even if the target value doesn't exist in the tree, the split should still happen based on the condition.

Important: The original parent-child relationships should be preserved as much as possible. That means if a node and its child both end up in the same subtree, they must still be connected in the same way as they were in the original tree.

Return an array of the two roots of the two subtrees in order.

Examples

Example 1:

• Input:

  • Binary Search Tree:

            4
           / \
          2   6
         / \   \
        1   3    7

  • Target: 5

• Output:

  • Split BST 1:

    • Tree 1 (Greater):

            6
             \
              7

    • Tree 2 (Smaller):

           4
          / \
         2   5
        /
       1
        \
         3

• Explanation:

  • In this example, the binary search tree is split based on the target value of 5.
  • All nodes greater than the target value (6, 7) are moved to Tree 1, while all nodes smaller than or equal to the target value (4, 2, 5, 1, 3) are moved to Tree 2.
  • The resulting Tree 1 contains nodes greater than 5, while Tree 2 contains nodes smaller than or equal to 5.

Example 2:

• Input:

  • Binary Search Tree:

            4
           / \
          2   6
         / \   \
        1   3    7

  • Target: 3

• Output:

  • Split BST 2:

    • Tree 1 (Greater):

            4
             \
              6
               \
                7

    • Tree 2 (Smaller):

           2
          / \
         1   3

• Explanation:

  • In this example, the binary search tree is split based on the target value of 3.
  • All nodes greater than the target value (4, 6, 7) are moved to Tree 1, while all nodes smaller than or equal to the target value (2, 1, 3) are moved to Tree 2.
  • The resulting Tree 1 contains nodes greater than 3, while Tree 2 contains nodes smaller than or equal to 3.

Example 3:

• Input:

  • Binary Search Tree:

            4
           / \
          2   6
         / \   \
        1   3    7

  • Target: 7

• Output:

  • Split BST 3:

    • Tree 1 (Greater):

            7

    • Tree 2 (Smaller):

           4
          / \
         2   6
        / \  
       1   3

• Explanation:

  • In this example, the binary search tree is split based on the target value of 7.
  • Only the root node (7) is greater than the target value and is moved to Tree 1.
  • The remaining nodes (4, 2, 6, 1, 3) are smaller than or equal to the target value and are moved to Tree 2.
  • The resulting Tree 1 contains only the root node 7, while Tree 2 contains all other nodes from the original tree.

The resulting subtrees are then connected to the appropriate sides of the root node, forming the split BST.

Constraints:

• The number of nodes in the tree is in the range [1, 50].
• 0 <= Node.val, target <= 1000

Try it yourself

Try solving this question here:

I just read a lesson on **18 Split BST** (DSA) and want to truly understand it. Explain 18 Split BST from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **18 Split BST** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **18 Split BST** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **18 Split BST** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.