# Binary Trees

"The most important concept in computer science" - Josh Hug

## Humble Origins

Linked lists are great, but we can do better! Let's try **rearranging the pointers **in an interesting way.

Instead of starting at one end of the list, let's set our first pointer at the **middle** of the list!

Now, let's make new pointers going to the **center **of each **sublist **on the left and right of the center.

Let's do it again!

Would ya look at that, we've got a **tree**! 🌲

## Types of Trees

Right now, we can determine some properties that all trees have.

All trees have a

**root node**.All nodes can point to

**child nodes.**Or, if they don't have any children, they are**leaves.**

We can add more and more constraints to our tree to make them more useful!

First, let's add the constraint that **node can only have 2 or fewer children **to create a **binary tree.**

Then, let's **ensure our tree is sorted **to create a **binary search tree. **A tree is sorted if it has these properties:

Every value in the

**left subtree**of a node is**less than**the node's value.Every value in the

**right subtree**of a node is**greater than**the node's value.Values are

**transitive**- there are**no duplicate values**.The tree is

**complete**- it is possible to**compare any two values**in the tree and say that one is**either less than or greater than the other.**The tree is

**antisymmetric**- If`p < q`

is true and`q < r`

is also true, then it must follow that`p < r`

.

## Tree Operations

There are **three important operations** that trees should support: **find, insert, and delete.**

**Find**

**Find**

Finding a value in a tree uses Binary Search. Click the link below to read up on it!

Binary Search### Insert

The insert algorithm is **very similar to binary search.** Here are the steps to take:

Search for the item.

**If it's found, then do nothing**since the value is already in the tree.If it's not found (search would return null in this case), then create a node and put it where it should be found. If using recursion, this last step is already done- all we need to do is return a new node!

Here's the algorithm:

### Delete

This one's a bit trickier because we need to make sure that the new tree still **preserves the binary search tree structure. **That means that we might have to shuffle around nodes after the deletion. There are **three cases:**

A) The node to delete is a **leaf**. This is an easy case- just remove that node and you're done!

B) The node to delete has **one child. **In this case, **swap** the node with its child, then **delete the node.**

C) The node to delete has **two children.** This one's trickier, because we still need to preserve the tree structure! In this case, we have to **traverse the node's children **to find the **next biggest value **and swap that up to replace the old node.

## Asymptotic Analysis

A binary tree can be **bushy **or **spindly. **These two cases have dramatically different performances!

**Bushy** trees are the **best case. **A tree is bushy if **every parent has exactly 2 children.**

A bushy tree is guaranteed to have a height of $\Theta(\log(n))$ which means that the runtimes for adding and searching will also be $\Theta(\log(n))$ .

**Spindly **trees are the **worst case. **A tree is spindly if **every parent has exactly 1 child. **This makes the tree essentially just a linked list!

A spindly tree has a height of $\Theta(n)$ which means that the runtimes for adding and searching will also be $\Theta(n)$ .

In Balanced BSTs, we will explore ways of guaranteeing that a tree is bushy!

## Limits of Trees

While trees are extremely versatile and fantastic for a variety of applications, trees have some limitations that make it difficult to use in some situations.

**All items in a tree need to be comparable.**We can't construct a binary tree out of categorical data, like models of cars, for example.**The data must be hierarchical.**If data can be traversed through in multiple ways, or forms loops, Graphs are probably better.**The best case runtime is**$\Theta(\log(n))$ . This might seem good, but other data structures like Tries and Hash Tables can be as good as

## Tree Traversals

Check out these pages for information on how to go through each element of a tree!

Depth First Search (DFS)Breadth First Search (BFS)Last updated