Most tree problems can be solved using recursions,  using O(N) time complexity and O(logN) space complexity. based on the pattern that each tree can be divided into root, a left subtree, and a right subtree, and the subtrees are essentially trees again.

For a binary search tree, its main property is that all the nodes on the left subtree are smaller than the root node, and all the nodes on the right subtree are larger than the root node. This gives us the opportunity to visit one of the subtrees, instead of both of the subtrees, achieving O(logN) time complexity and O(logN) space complexity.

701. Insert into a Binary Search Tree

Insert to left subtree if the root value is larger than the target, insert to right subtree if the root value is smaller than the target, and create a single node tree is the tree is empty. Update the left pointer / right pointer to points to the tree after insertion.

450. Delete Node in a BST

Delete in the left subtree if the root value is larger than the target, delete in the right subtree if the root value is smaller than the target, and delete the root node if it is equal to the target.

When the root is deleted, if the original tree has only one node, return an empty tree; if the original tree has only one child, promote the child as the root; if the original tree has two children, promote the right child as the root, find the successor of the deleted root, and demote the left child as the left child of the successor.

776. Split BST

Find the root of the smaller tree and the larger tree on each level of recursion. When the root is larger than the target, the smaller nodes of the left subtree is the smaller nodes of the current tree, and the root is calculated from the recursion; the larget nodes of the left subtree, the root, and the right subtree is the larger nodes of the current tree, and the root is the current node. Vice versa.