by Yung L. Leung

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

Photo by Keith Wickramasekara on Unsplash

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

source

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.

A root branches off into two parents of leaves. Leaves (green) are nodes without children.

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.

Insertion of the node with a value of 6

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.

Finding the node with a value of 6

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.

Breadth First Search returns [3, 1, 5, 0, 2, 4, 6]

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.

Depth First Search Pre — Order returns [3, 1, 0, 2, 5, 4, 6]

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).

n = 3

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

Photo by Nick Tong on Unsplash

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).

Max 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.

Insertion of a node with a value of 6 & bubbling it upward.

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.

Extraction of the max node with the value of 6 & sinking down node with the value of 3.

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.

Bubbling up of the new node with value 6
  • 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.

Sinking down of node with value 1
  • 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/