# Recca Chao 的 gitHub page

## 推廣網站開發，包含 Laravel 和 Kotlin 後端撰寫、自動化測試、讀書心得等。Taiwan Kotlin User Group 管理員。

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
``````