Hi, here’s your problem today. This problem was recently asked by Twitter:

Given a binary search tree (BST) and a value s, split the BST into 2 trees, where one tree has all values less than or equal to s, and the other tree has all values greater than s while maintaining the tree structure of the original BST. You can assume that s will be one of the node’s value in the BST. Return both tree’s root node as a tuple.

Here’s an example and some starting code:

```
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def __repr__(self):
if self.left and self.right:
return f"({self.value}, {self.left}, {self.right})"
if self.left:
return f"({self.value}, {self.left})"
if self.right:
return f"({self.value}, None, {self.right})"
return f"({self.value})"
def split_bst(bst, s):
# Fill this in.
n2 = Node(2)
n1 = Node(1, n2)
n5 = Node(5)
n4 = Node(4, None, n5)
root = Node(3, n1, n4)
print(root)
# (3, (1, (2)), (4, None, (5)))
# How the tree looks like
# 3
# / \
# 1 4
# \ \
# 2 5
print(split_bst(root, 2))
# ((1, (2)), (3, None, (4, None, (5))))
# Split into two trees
# 1 And 3
# \ \
# 2 4
# \
# 5
```