LeetCode: 776 Split BST

•

admin

LeetCode 776: Split BST

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

Problem Description

Given a Binary Search Tree (BST) and a value V, split the tree into two subtrees. One subtree should contain all nodes with values less than or equal to V, and the other subtree should contain all nodes with values greater than V. Return the root nodes of these two subtrees as a list of length 2.

Example 1:

Input: root = [4,2,6,1,3,5,7], V = 2
Output: [[2,1],[4,3,6,null,null,5,7]]
Explanation:
The input BST is structured as follows:
       4
     /   \
    2     6
   / \   / \
  1   3 5   7

The two resulting BSTs are:
1. Subtree with nodes less than or equal to 2:
       2
     /
    1

2. Subtree with nodes greater than 2:
       4
     /   \
    3     6
         / \
        5   7

Solution Approach

This is a recursive problem that can be solved by leveraging the properties of a BST. Based on the value of root.val and the splitting value V, we recursively split the tree into two parts:

  • If root.val <= V: The current node and its left subtree belong to the subtree with values less than or equal to V. To ensure that nodes greater than V are correctly assigned, we recursively split root.right. The left subtree of the result will be attached back to root.right, and the larger part will be returned as the right subtree.

  • If root.val > V: The current node and its right subtree belong to the subtree with values greater than V. To ensure that nodes less than or equal to V are correctly assigned, we recursively split root.left. The right subtree of the result will be attached back to root.left, and the smaller part will be returned as the left subtree.

Finally, we return these two subtrees as a list of length 2.

Code Implementation

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, V: int):
        if not root:
            return [None, None]

        if root.val <= V:
            # Current node and its left subtree belong to the <= V subtree
            left_tree, right_tree = self.splitBST(root.right, V)
            root.right = left_tree  # Attach the <= V part to root's right subtree
            return [root, right_tree]  # Return the current node and right subtree

        else:
            # Current node and its right subtree belong to the > V subtree
            left_tree, right_tree = self.splitBST(root.left, V)
            root.left = right_tree  # Attach the > V part to root's left subtree
            return [left_tree, root]  # Return left subtree and current node

Code Explanation

  1. Base Case:

    • When root is None, return [None, None], indicating there are no subtrees to split.

  2. Recursive Decision:

    • If root.val <= V, the current node and its left subtree belong to the subtree with values less than or equal to V. We recursively split root.right and attach the result’s left subtree to root.right.
    • If root.val > V, the current node and its right subtree belong to the subtree with values greater than V. We recursively split root.left and attach the result’s right subtree to root.left.

  3. Return Values:

    • The function returns two subtrees: the first containing all nodes less than or equal to V and the second containing all nodes greater than V.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once to perform the split.
  • Space Complexity: O(n), due to the recursive stack depth, which can reach up to n in the worst case when the tree is skewed.

Example Walkthrough

Example 1:

Input: root = [4,2,6,1,3,5,7], V = 2
  • Root node root.val = 4, since 4 > V = 2, we recursively process root.left.
  • For root.left = 2, since 2 <= V, we recursively process root.right, which is node 3.
  • The final result is two subtrees:
1. Subtree with nodes <= 2:
    2
   /
  1

2. Subtree with nodes > 2:
    4
   /   \
  3     6
       / \
      5   7

Detailed Explanation of the Recursion (Using the Binary Search Tree Split Example)

Let’s take the following binary search tree (BST) as an example:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Suppose we want to split the BST using V = 6 as the dividing point. This means that:

  • One subtree will contain all the nodes with values less than or equal to 6.
  • The other subtree will contain all the nodes with values greater than 6.

We can use recursion to solve this problem. Here’s a step-by-step explanation of the recursive process.

Core Logic of the Recursion:

  1. If the current node’s value <= V: The current node and its left subtree belong to the "less than or equal to V" subtree. We need to recursively split its right subtree.
  2. If the current node’s value > V: The current node and its right subtree belong to the "greater than V" subtree. We need to recursively split its left subtree.

Recursion Process:

  1. Start from the root node 8:

    • The current node 8 is greater than V = 6, so 8 and its right subtree (i.e., 10 and its children) should be part of the "greater than 6" subtree.
    • Recursively process root.left = 3 to handle the "less than or equal to 6" subtree.

  2. Process node 3:

    • The current node 3 is less than V = 6, so 3 and its left subtree (1) belong to the "less than or equal to 6" subtree.
    • However, node 3’s right subtree is 6, which is equal to V. We need to recursively process root.right = 6 to split this subtree.

  3. Process node 6:

    • The current node 6 is exactly equal to V = 6, so 6 and its left subtree (4) belong to the "less than or equal to 6" subtree.
    • However, node 6 has a right child 7, which is greater than 6. We need to move 7 to the "greater than 6" subtree.
    • Recursively process root.right = 7 and return [None, 7], meaning 7 will be part of the "greater than 6" subtree, and 6’s right subtree is set to None.

  4. Back to node 3:

    • Now, node 6 has its right subtree set to None (since 7 has been moved). The left subtree of 6 remains unchanged, so 6 and its subtree are part of the "less than or equal to 6" subtree.
    • Node 3’s left subtree remains 1, and its right subtree is now 6. Thus, node 3 and its subtrees belong to the "less than or equal to 6" portion.
    • Recursively return [3, 8], indicating that nodes <= 6 are in the subtree rooted at 3, and nodes > 6 are in the subtree rooted at 8.

  5. Process the right subtree 10 and 14:

    • Back to the root 8, since 8 > 6, the previously processed right subtree remains the same: 10 and its subtree remain part of the "greater than 6" subtree.

Final Split Result:

  • Subtree with nodes less than or equal to 6:

      3
 / \
1   6
   /
  4

  • Subtree with nodes greater than 6:

      8
   \
   10
     \
     14
    /
   13
  /
 7

Key Points of the Recursion:

  1. Recursively Splitting the Left and Right Subtrees:

    • For each node, we decide whether to recursively split its left or right subtree based on its value compared to V.
    • Nodes less than or equal to V recursively split their right subtree, and nodes greater than V recursively split their left subtree.

  2. Backtracking and Rebuilding the Subtrees:

    • After recursively processing a node’s left or right subtree, the node attaches the resulting subtrees back to itself, preserving the binary search tree structure.

  3. Maintaining the BST Property:

    • Throughout the recursion, the binary search tree property is maintained: left children are less than the current node, and right children are greater than the current node.

By using recursion, we can effectively split the entire tree into two parts, one containing nodes less than or equal to V, and the other containing nodes greater than V.

Post Views: 29

•

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *