# Binary Search Trees

The power of Binary search trees comes from the speed at which this algorithm can deliver results.

What makes Binary Search trees so fast, are the two main rules we follow when implementing the binary tree structure.

At a very basic level, binary trees have two parts:

**Part 1**: A binary search tree has at least 2 binary trees within it, a left subtree and a right subtree. The binary tree should be balanced, meaning each parent node can have a maximum of 2 child nodes. Trees are recursive structures, which means that a single tree is made up of many other subtrees.

**Part 2**: Nodes are sorted. This requirement will ensure searching through Binary Search trees is very fast.

Everything we insert to the right of the root node will be larger in value than the root node. Everything we insert to the left of the root node must be smaller in value.

ifroot.val==key:returnrootelifroot.val < key:root.right=insert(root.right, key)else:root.left=insert(root.left, key)

These two simple rules allow binary search trees to leverage the power and speed of the *Binary Search Algorithm*. The Binary search algorithm divides the data set into two parts every time it takes a step! We reduce the amount of searching by half every time we take a step. This makes searching and inserting so much faster!

Binary Search trees will not work if the tree is not balanced. Once unbalanced, Binary Search trees cannot leverage the speed-superpower of the *Binary Search Algorithm.*

Search insertion and deletion have a best-case time complexity of O(log n), unbalanced trees can degrade big complexity to that of a singly linked list.

Binary search trees have so many useful applications, take for example scheduling flights coming in on a busy airport runway. Binary trees are a very efficient structure to use in this case, because of their sorted nature. A request to land at a certain time can be easily serviced by the Binary Tree. Searching and insertion speed is not the only superpower Binary Trees have, extra constraints can be built in at insertion so that permission to land at a certain time given some restraints will or will not be granted. For example: In our airport, let's assume flights are scheduled to land every 3 minutes. We will call this constraint K=3. Traversing down the tree to find a time is quick because we are using Binary search, upon insertion, we can have the node checked to make sure our constraint K is met. If our node to be inserted is within 3 minutes of other existing nodes, in this case, if planes are only to land 3 minutes apart from each other, we have to have a method in place so that a plane requesting to land at 3:05 can only do so if the previous plane landed at 3:02 and the next plane lands at 3:08 insertion has to fail if the K constraint is not met. Pretty great use of BST’s !

Resources:

MIT Open Courseware (2013) *Binary Search Trees, BST Sort* https://youtu.be/9Jry5-82I68

Yourbasic.org *Binary Search Trees Explained* https://yourbasic.org/algorithms/binary-search-tree/

Vaidehi Joshi(2018) *Trees & Binary Search Tree *https://dev.to/vaidehijoshi/trees--binary-search-trees--basecs-video-series-5e38