# Data structure - Binary Search Tree

Binary Search Trees are Binary trees that have the following properties:

1. At most 2 child nodes per node.
2. Any nodes on the left are less than the parent node (including sub-tree).
3. Any node on the right are greater than the parent node (including sub-tree).

### Inserting / Building BST

The BST properties must be maintain BST properties even when inserting a node into a BST. There are two cases to handle when inserting a node in BST:

1. Inserting a node at root (root = null).
2. Inserting into a node that has child nodes.

Inserting a node into the root involves creating a new node and assign it to the root. All subsequent node insertions will start from this root. When inserting into a node with children we have to evaluate all its child nodes until we reach a leaf. We place the node left or right depending on if the node value is less or greater than the value we are inserting (respectively).

### Searching BST

The BST data structure references the root node. From the root node of a BST we can traverse the tree of nodes and reach any child node in the tree. Using the BST shown above when we try to locate 72 we do the following:

1. Start with root.
2. If node has children, evaluate:
if node.value < 72, advance to right node (where bigger node.value would be located)
if node.value > 72, advance to left node (where smaller node.value would be located)
3. Traverse all the way to leaf until node.value is found.

Below diagram depicts the above steps to locate the value of 72.

### Deleting a node

When deleting a node in a tree we need to remove all the references to the node to be deleted. The child nodes in BST do not have a reference to the parent node. This means when deleting a node we need to be operate on the parent node.

There are 3 cases to consider:

1. Deleting a node at the leaf
2. Deleting a node with children
3. Deleting a node that is the parent of 2 child nodes.

### Finding Min/Max

operation description
min left most node in a BST
max right most node in a BST

### BST - Code example

Below shows code to build BST using recursion:

## BST Traversal

### Traversal - in-order

1. Traverse left subtree (and all its sub-trees)
2. root
3. Traverse right subtree (and all its sub-trees)

### Traversal - pre-order

1. root
2. Traverse left subtree (and all its sub-trees)
3. Traverse right subtree (and all its sub-trees)

### Traversal - post-order

1. Traverse left subtree (and all its sub-trees)
2. Traverse right subtree (and all its sub-trees)
3. root

## Balancing BST

There are technique that can maintain the balance of a tree. For example AVL, Red-Back tree etcâ€¦

### BST height

Earlier we came across examples where the data and operations can cause a BST to become unbalanced. Un balanced tree affect the performance of BST operations because the time complexity of the operations are proportional to the height of the BST.

Below we will show that in a balanced BST tree, the height of the BST is logarithmic scale of the total number of nodes:

## Time Complexity - BST Operation

Note that we are assuming that the BST is balanced.

operation T(n) Complexity comment
Search O(log(2)n) searching worst case search would be the full height of the tree.
Insertion O(log(2)n) + O(1) searching for the node + pointer changes.
Deletion O(log(2)n) + O(1) searching for the node + pointer changes.
Min O(log(2)n)
Max O(log(2)n)