by Yung L. Leung

# Binary data structures: an intro to trees and heaps in JavaScript

**Linear data structures** are simple in direction. A **linked list** is a list of nodes (each containing their own data) that are linked from one node to the next (and to the previous, for a doubly linked list). A **stack** builds upward like a tower of data. Each node stacking atop another, and shortens in a **last in first out (**LIFO**)** manner. A **queue** is a line of nodes that elongate from the end of the line and shortens in a **first in first out (**FIFO**)** mechanism.

**Binary data structures **are like a fork in a road of data. The nodes build like the branches of a **tree** or a **heap** of rocks.

### Trees

A **binary search tree** is made up of nodes that branch off to no more than two nodes (binary). A parent node can have left and right child nodes. By convention, left child nodes contain values less than the parent. Whereas right child nodes contain greater values (**left is less, right is greater**). All trees begin with a single root node.

To **insert** a value requires creating a **new node**, comparing its value to the **root **& its **descendant** values, while deciding to search further leftward (insertion of lesser value) or rightward (insertion of greater value). Once an available position is found, the node is inserted in place.

To **find** a value is similar to the insertion of a value. You are performing the search for a stored value and returning the node containing it.

To make a **breadth-first search** of values requires storing a root value. Then proceeding with the left child, then the right child and so forth.

To make a **depth-first search (**pre-order**)** of values requires storing a root value. Then proceeding with all leftward descendants, before the rightward descendants.

Since **inserting** & **finding** a node of some value are relatively similar processes (insertion inserts a node whereas finding returns a node), it is of no surprise that their complexity is the same, **O(log n)**.

For a 3 node **binary search tree**, to **find** **5** requires two steps:

- Is
**5**greater than or less than 3? Proceed rightward. - Is
**5**equal to the value being searched? Return node.

Similarly to **insert** a node with value 6 requires two steps:

- Is
**6**greater than or less than 3? Proceed rightward. - Is
**6**greater than or less than 5? Insert the right side.

### Heaps

A **binary heap** is a pyramidal structure of nodes whose nodes can stack upward with rows of decreasing values toward a minimum (**minimum binary heap**) or with rows of increasing values toward a maximum (**maximum binary heap**). Like the tree, each parent node can extend up to two child nodes. Unlike the tree, each parent can contain a lesser value than its children (**minimum binary heap**) or a greater value (**maximum binary heap**).

For a **max binary heap**, to **insert** a value at the base of the pyramid requires comparing it to parent nodes and **bubbling up** the larger value.

To **extract a max** value requires removing the apex value and **sinking down** a value from the pyramid’s base. This involves finding the higher of the two children nodes.

For a **max binary heap**, **insertion** of a node & **extraction** of a node with the max value both has a complexity of **O(log n)**.

For a 3 node **max binary heap**, insertion of a node with value 6 requires two steps.

- Upon attaching node of value 6 to a new row (below 4), is
**6**greater than or less than 4? Swap. - Is
**6**greater than or less than 5? Swap.

Similarly, after the removal of a node with a max value & replacing it with a node of value **1**, two steps remain.

- Is
**1**greater than or less than 5? Swap. - Is
**1**greater than or less than 4? Swap.

Thank you for reading!

### Reference:

https://www.udemy.com/js-algorithms-and-data-structures-masterclass/