Split BST

class Solution {
public:
    vector<TreeNode*> partitionBST(TreeNode* root, int value) {
        TreeNode* leftDummy = new TreeNode(0);
        TreeNode* left = leftDummy;
        TreeNode* rightDummy = new TreeNode(0);
        TreeNode* right = rightDummy;
    
        TreeNode* node = root;
        TreeNode* temp = nullptr;
    
        while (node != nullptr) {
            if (node->val <= value) {
                left->right = node;
                left = node;
                temp = node->right;
                left->right = nullptr;
                node = temp;
            } else {
                right->left = node;
                right = node;
                temp = node->left;
                right->left = nullptr;
                node = temp;
            }
        }
    
        return {leftDummy->right, rightDummy->left};
    }
};

The provided C++ function partitionBST splits a binary search tree into two subtrees based on a specified value. The function returns a vector containing pointers to the roots of the two resulting subtrees: one subtree contains all nodes with values less than or equal to the given value, and the other contains nodes with values greater.

• Initialize two dummy nodes, leftDummy and rightDummy, to simplify the process of building the left and right subtrees.
• Use left and right pointers to manage the current end of the growing subtrees.
• Traverse the given BST using a node pointer. Compare the value of the current node with the input value:
  • If the node's value is less than or equal to the provided value, attach it to the right child of the left node. Move the left pointer to this node and sever the node's right link to isolate it from its original tree structure before moving on.
  • If the node's value is greater than the input value, attach it to the left child of the right node. Move the right pointer and sever the node's left link.
• Continue this process until no nodes are left to process.
• The function concludes by returning a vector of two elements: the right child of leftDummy and the left child of rightDummy. These represent the roots of the two required subtrees.

With this approach, ensure all nodes get correctly reassigned to the appropriate subtree without losing any nodes or reference links.

class Solution {
    
    public static TreeNode[] divideBST(TreeNode rootNode, int splitVal) {
        // Create placeholders for smaller and larger partitions
        TreeNode smallDummy = new TreeNode(0);
        TreeNode smallCurrent = smallDummy;
        TreeNode largeDummy = new TreeNode(0);
        TreeNode largeCurrent = largeDummy;
    
        // Begin with the root node
        TreeNode iterate = rootNode;
        TreeNode futureNode;
    
        while (iterate != null) {
            if (iterate.val <= splitVal) {
                // Link iterate node to small partition
                smallCurrent.right = iterate;
                smallCurrent = iterate;
    
                // Go to right child since left is guaranteed smaller
                futureNode = iterate.right;
                    
                // Detach current node from its right child
                smallCurrent.right = null;
    
                iterate = futureNode;
            } else {
                // Link iterate node to large partition
                largeCurrent.left = iterate;
                largeCurrent = iterate;
    
                // Go to left child since right is guaranteed bigger
                futureNode = iterate.left;
    
                // Detach current node from its left child
                largeCurrent.left = null;
    
                iterate = futureNode;
            }
        }
    
        // Return trees from dummy nodes
        return new TreeNode[] { smallDummy.right, largeDummy.left };
    }
}

The Split BST problem involves dividing a Binary Search Tree (BST) into two separate trees based on a given value: splitVal. The trees returned are such that one contains all values less than or equal to splitVal, and the other contains all values greater than splitVal. Here's how the solution in Java addresses this problem:

1. Initialize two dummy nodes, smallDummy and largeDummy, to act as placeholders for the roots of the two new trees. Additional pointers, smallCurrent and largeCurrent, are used to build these trees iteratively.

2. Start from the root node of the given BST and traverse it. Based on the comparison of the current node's value with splitVal, decide in which tree the current node should be placed:

   • If the current node value is less than or equal to splitVal, attach it to the right of the smallCurrent tree. Then move smallCurrent to point to this node.
   • If the current node value is greater than splitVal, attach it to the left of the largeCurrent tree. Then move largeCurrent to point to this node.

3. After linking a node to its respective tree, detach it from its current subtree to avoid lingering connections that might cause a cycle or incorrect tree structure.

4. Continue the traversal by moving to the next relevant child node that could potentially contain values satisfying the conditions for the respective sub-trees (right child for the small tree, left child for the large tree).

5. Once the entire BST has been traversed and all nodes have been appropriately placed, the trees are extracted from the dummy nodes. The right child of smallDummy becomes the root of the small tree, and the left child of largeDummy becomes the root of the large tree.

6. Finally, return these roots as an array of nodes, completing the division of the BST based on splitVal.

This method ensures that the BST is split based on the value, maintaining the properties of BSTs in both resultant trees.

class Solution:
    def divideBST(self, root: TreeNode, limit: int) -> list[TreeNode]:
        # Temporary nodes for constructing smaller and larger BST parts
        small_root_placeholder = TreeNode(0)
        small_current = small_root_placeholder
        large_root_placeholder = TreeNode(0)
        large_current = large_root_placeholder
    
        # Main loop to navigate tree
        node_pointer = root
        next_pointer = None
    
        while node_pointer is not None:
            if node_pointer.val <= limit:
                # Link node to the 'less than or equal' part
                small_current.right = node_pointer
                small_current = node_pointer
    
                # Prepare for the next iteration on the right subtree
                next_pointer = node_pointer.right
                small_current.right = None
    
                node_pointer = next_pointer
            else:
                # Link node to the 'greater than' part
                large_current.left = node_pointer
                large_current = node_pointer
    
                # Prepare for the next iteration on the left subtree
                next_pointer = node_pointer.left
                large_current.left = None
    
                node_pointer = next_pointer
    
        # Return both parts of the divided BST
        return [small_root_placeholder.right, large_root_placeholder.left]

The provided Python solution defines a function divideBST within a Solution class to split a binary search tree (BST) based on a defined limit. The function splits the BST into two sub-trees: one containing nodes with values less than or equal to the limit, and the other containing nodes with values greater than the limit.

Here's how the function operates:

• Initializes placeholders for the roots of two new BSTs, small_root_placeholder for nodes less than or equal to limit, and large_root_placeholder for nodes greater than limit.
• Iteratively traverses through the original BST using node_pointer. During each iteration, it checks the current node's value against limit:
  • If the current node's value is less than or equal to limit, it gets appended to the right of the small_current tree.
  • If the current node's value exceeds limit, it gets appended to the left of the large_current tree.
• After each iteration, pointers are adjusted appropriately to exclude the linked node from further consideration, preventing duplication in the split BSTs.
• The traversal continues until all nodes have been considered and properly allocated to either the small_root_placeholder or large_root_placeholder sub-tree.
• The function returns both parts of the divided BST as a list containing the right child of small_root_placeholder and the left child of large_root_placeholder, which represent the two new root nodes, respectively.

The algorithm efficiently divides the entire BST with a single tree traversal, ensuring minimal time complexity ideally close to O(n), where n is the number of nodes in the BST. It uses direct pointer manipulation to build the new trees, avoiding the creation of additional data structures, thus optimizing memory usage.