# Leetcode:Binary Search Tree

### 一道LeetCode题目

Given a binary search tree and the lowest and highest boundaries as `L` and `R`, trim the tree so that all its elements lies in [`L`, `R`] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.:287 (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.

### BST数据结构的一些算法特性

Algorithm Average Worst case
Space O(n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

1、Leetcode
2、Wiki Binary search tree

# cocowool

A FULL STACK DREAMER!