A binary search tree is an ordered binary tree. The left subtree contains nodes whose keys are less than the node’s key value, while the right subtree contains nodes whose keys are greater than or equal to the node’s key value. Moreover, both subtrees are also binary search trees. A binary search tree can retrieve data efficiently.

Part 1 – Binary tree implementation
Part 2 – Binary search tree implementation
Part 3 – Binary search tree with parent pointer

### Define classes

The TreeNode in binary search tree is the same as regular binary tree. It has three attributes, data, left and right. data is the data stored in this node. Its data type can be anything such as Integer, String or objects. left is the left child. right is the right child. Their data type is TreeNode.

After we define TreeNode, we can define BinarySearchTree class. It has one attribute, root. It is the node from where most tree operations start.

Please note, since binary search tree is ordered, in Java, BinarySearchTree’s generic data type extends Comparable interface, so that we can compare data in insert, delete or search operations.

## Python

### Insert

In order to insert a value to a binary search tree, we have to find the right spot. From the root, we compare the value with each node’s data. If the value is larger than the node’s data, we move to right child. Otherwise move to the left child, until the node’s left or right child is null. Then we can add the new node with the input value as left or right child.

## Doodle

### Delete by key

Delete a node in binary search tree is easier than delete a node in binary tree. We always promote the inorder successor of deleted node. So it will be right child’s left most descendent. If right child is null, promote left child.

Besides, we don’t need to go through all the nodes in the tree to search. We can just follow the path based on the comparison of node’s data with the input key. So the time complexity is O(h), h is the height of the tree.

## Doodle

### Search by key

There are two ways to search, Depth first search and Breadth first search.

Depth first search (DFS) starts from the root, and explores the child nodes as far as possible before backtracking. DFS is usually implemented with recursion or stack.

Breath First Search (BFS) starts from the root, and explores all its children before going to the next level. BFS is usually implemented with Queue.

Just like delete, both DFS and BFS in binary search tree has time complexity of O(h). The search doesn’t need to go through all the nodes in the tree. It follows the path based on the comparison of node’s data with the input key.

## Doodle

### Traversal

The traversal is to visit all nodes in the binary search tree. It is the same as binary tree, including inorder, preorder, postorder and level order.

Inorder is to traverse the left subtree, visit the root, traverse the right subtree. In binary search tree, the output of the key should be in ascending order.

Preorder is to visit the root, traverse the left subtree, traverse the right subtree.

Postorder is to traverse the left subtree, traverse the right subtree, visit the root.

Level order is to traverse the nodes level by level.

please refer to the traversal of binary tree for the implementation.