DS with JS — Trees

Trees are similar to the trees 🌳 in nature with one subtle difference — the trees we are going to learn are upside down.

Trees Vocabulary | Made with Excalidraw

Trees are non-linear data structures. This is not the one-after-the-other structure that is classified as a linear data structure. Arrays, stacks, queues, or linked lists are linear data structures. In trees, we can have elements like branches, actual tree branches — anywhere!

This flexibility introduces a need to build a vocabulary for trees and learn to classify them. We will explore a very specific and famous binary tree and implement it in JavaScript.

Building our Vocabulary for Trees

We understand node from Linked Lists. In Singly Linked List a node has a value and a pointer to the next node. The last node in the (singly/doubly) linked list points to null. A tree is made up of nodes as well. But as you would have guessed they are not arranged one after the other.

A linked list is a Degenerate or Pathological Tree.

Now that we understand the most fundamental element of a tree — node, let us build the vocabulary for trees.

1. Root Node: The top node which has no nodes pointing to it. This is the start of the tree.