Tree Data Structure in JavaScript

1 What is a Tree Data Structure?

A tree is a non-linear and hierarchical data structure consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the "children").

This data structure is a specialized method to organize and store data in the computer to be used more effectively. It consists of a central node, structural nodes, and sub-nodes, which are connected via edges. We can also say that tree data structure has roots, branches, and leaves connected with one another.

Recursive Definition:

A tree consists of a root, and zero or more subtrees T1, T2, ... Tk such that there is an edge from the root of the tree to the root of each subtree.

Why Tree is considered a non-linear data structure?

The data in a tree are not stored in a sequential manner i.e., they are not stored linearly. Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For this reason, the tree is considered to be a non-linear data structure.

2 Tree Terminologies

Parent Node: The node which is a predecessor of a node is called the parent node of that node.
Child Node: The node which is the immediate successor of a node is called the child node of that node.
Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.
Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes.
Ancestor of a Node: Any predecessor nodes on the path from the root to that node are called Ancestors of that node.
Descendant: Any successor node on the path from the leaf node to that node.
Sibling: Children of the same parent node are called siblings.
Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.
Internal node: A node with at least one child is called Internal Node.
Neighbour of a Node: Parent or child nodes of that node are called neighbors of that node.
Subtree: Any node of the tree along with its descendant.

3 Properties of a Tree

Number of edges: An edge can be defined as the connection between two nodes. If a tree has N nodes then it will have N-1 edges. There is only one path from each node to any other node of the tree.
Depth of a node: The depth of a node is defined as the length of the path from the root to that node. Each edge adds 1 unit of length to the path. So, it can also be defined as the number of edges in the path from the root of the tree to the node.
Height of a node: The height of a node can be defined as the length of the longest path from the node to a leaf node of the tree.
Height of the Tree: The height of a tree is the length of the longest path from the root of the tree to a leaf node of the tree.
Degree of a Node: The total count of subtrees attached to that node is called the degree of the node. The degree of a leaf node must be 0. The degree of a tree is the maximum degree of a node among all the nodes in the tree.

4 Why Tree?

Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure. One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer:

       file system
        /    <-- root
       /      \
     ...      home
           /        \
       ugrad        course
        /            /      |     \
      ...          cs101  cs112  cs113

If we organize keys in form of a tree (with some ordering e.g., BST), we can search for a given key in moderate time (quicker than Linked List and slower than arrays). Self-balancing search trees like AVL and Red-Black trees guarantee an upper bound of O(Log n) for search.
We can insert/delete keys in moderate time (quicker than Arrays and slower than Unordered Linked Lists). Self-balancing search trees like AVL and Red-Black trees guarantee an upper bound of O(Log n) for insertion/deletion.
Like Linked Lists and unlike Arrays, Pointer implementation of trees don't have an upper limit on number of nodes as nodes are linked using pointers.

5 Types of Tree data structures

General tree: A general tree data structure has no restriction on the number of nodes. It means that a parent node can have any number of child nodes.
Binary tree: A node of a binary tree can have a maximum of two child nodes. In the given tree diagram, node B, D, and F are left children, while E, C, and G are the right children.
Balanced tree: If the height of the left sub-tree and the right sub-tree is equal or differs at most by 1, the tree is known as a balanced tree.
Binary search tree: As the name implies, binary search trees are used for various searching and sorting algorithms. The examples include AVL tree and red-black tree. It is a non-linear data structure. It shows that the value of the left node is less than its parent, while the value of the right node is greater than its parent.

6 Applications of Tree

Store hierarchical data, like folder structure, organization structure, XML/HTML data.
Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data. It also allows finding closest item.
Heap is a tree data structure which is implemented using arrays and used to implement priority queues.
B-Tree and B+ Tree : They are used to implement indexing in databases.
Syntax Tree: Scanning, parsing, generation of code and evaluation of arithmetic expressions in Compiler design.
K-D Tree: A space partitioning tree used to organize points in K dimensional space.
Trie : Used to implement dictionaries with prefix lookup.
Suffix Tree : For quick pattern searching in a fixed text.
Spanning Trees and shortest path trees are used in routers and bridges respectively in computer networks.
As a workflow for compositing digital images for visual effects.
Decision trees.
Organization chart of a large organization.
In XML parser.
Machine learning algorithm.
For indexing in database.
IN server like DNS (Domain Name Server).
In Computer Graphics.
To evaluate an expression.
In chess game to store defense moves of player.
In java virtual machine.

7 Binary Tree Traversals

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc.), which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees:

Inorder (Left, Root, Right)
Preorder (Root, Left, Right)
Postorder (Left, Right, Root)

Inorder Traversal

In Inorder traversal, a node is processed after processing all the nodes in its left subtree. The right subtree of the node is processed after processing the node itself.

Algorithm Inorder(tree)

Traverse the left subtree, i.e., call Inorder(left->subtree)
Visit the root.
Traverse the right subtree, i.e., call Inorder(right->subtree)

Uses of Inorder Traversal: In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.

JavaScript Implementation:

class Node {
  constructor(k) {
    this.key = k;
    this.left = null;
    this.right = null;
  }
}
 
function inorder(root) {
  let ans = "";
  if (root !== null) {
    ans += inorder(root.left);
    ans += root.key + " ";
    ans += inorder(root.right);
  }
  return ans;
}
 
// Example Output
// 10 20 30 40 50

Preorder Traversal

In preorder traversal, a node is processed before processing any of the nodes in its subtree.

Algorithm Preorder(tree)

Visit the root.
Traverse the left subtree, i.e., call Preorder(left->subtree)
Traverse the right subtree, i.e., call Preorder(right->subtree)

Uses of Preorder: Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions on an expression tree.

JavaScript Implementation:

class Node {
  constructor(k) {
    this.key = k;
    this.left = null;
    this.right = null;
  }
}
 
function preorder(root) {
  let ans = "";
  if (root !== null) {
    ans += root.key + " ";
    ans += preorder(root.left);
    ans += preorder(root.right);
  }
  return ans;
}
 
// Example Output
// 10 20 30 40 50

Postorder Traversal

In post order traversal, a node is processed after processing all the nodes in its subtrees.

Algorithm Postorder(tree)

Traverse the left subtree, i.e., call Postorder(left->subtree)
Traverse the right subtree, i.e., call Postorder(right->subtree)
Visit the root.

Uses of Postorder: Postorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree.

JavaScript Implementation:

class Node {
  constructor(k) {
    this.key = k;
    this.left = null;
    this.right = null;
  }
}
 
function postorder(root) {
  let ans = "";
  if (root !== null) {
    ans += postorder(root.left);
    ans += postorder(root.right);
    ans += root.key + " ";
  }
  return ans;
}
 
// Example Output
// 20 40 50 30 10

8 Advanced Tree Operations

1. Height of Binary Tree

Given a binary tree, the task is to find the height of the tree. Height of the tree is the number of edges in the tree from the root to the deepest node. Height of the empty tree is 0.

Approach: Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1.

If the tree is empty, return 0.
Otherwise:
- Get the max depth of the left subtree recursively.
- Get the max depth of the right subtree recursively.
- Get the max of max depths of left and right subtrees and add 1 to it for the current node.

function height(root) {
  if (root === null) return 0;
  return 1 + Math.max(height(root.left), height(root.right));
}

Time Complexity: O(N) Auxiliary Space: O(N) due to recursive stack.

2. Print Nodes at K Distance

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root. The problem can be solved using recursion.

Approach:

If it's true print the node – Always check if the K distance === 0 at every node.
The left or right subtree – Decrement the distance by 1 when you are passing to its subtree (k - 1).

function printKDist(root, k) {
  let ans = "";
  if (root === null) return ans;
  
  if (k === 0) {
    ans += root.key + " ";
  } else {
    ans += printKDist(root.left, k - 1);
    ans += printKDist(root.right, k - 1);
  }
  return ans;
}

Time Complexity: O(N) where N is number of nodes in the given binary tree. Space Complexity: O(h) where h is the height of the binary tree.

3. Level Order Traversal of a Binary Tree

We have seen the three basic traversals (Preorder, Postorder, and Inorder). We can also traverse a Binary Tree using the Level Order Traversal. In the Level Order Traversal, the binary tree is traversed level-wise starting from the first to last level sequentially.

Algorithm: The Level Order Traversal can be implemented efficiently using a Queue.

Create an empty queue q.
Push the root node of tree to q. That is, q.push(root).
Loop while the queue is not empty:
- Pop the top node from queue and print the node.
- Enqueue node's children (first left then right children) to q.
- Repeat the process until queue is not empty.

function levelOrder(root) {
  if (root === null) return;
  
  let queue = [];
  queue.push(root);
  
  let result = [];
  
  while (queue.length > 0) {
    let curr = queue.shift();
    result.push(curr.key);
    
    if (curr.left !== null) {
      queue.push(curr.left);
    }
    if (curr.right !== null) {
      queue.push(curr.right);
    }
  }
  
  console.log(result.join(" "));
}

Time Complexity: O(N), where N is the number of nodes in the Tree. Auxiliary Space: O(N) for the queue.

4. Maximum in Binary Tree

Given a Binary Tree, find the maximum (or minimum) element in it.

Approach: In a Binary Search Tree, we can find maximum by traversing right pointers until we reach the rightmost node. But in a generic Binary Tree, we must visit every node to figure out the maximum. So the idea is to traverse the given tree and for every node return the maximum of 3 values:

Node's data.
Maximum in node's left subtree.
Maximum in node's right subtree.

function findMax(root) {
  if (root === null) {
    return Number.MIN_SAFE_INTEGER;
  }
  
  let res = root.key;
  let lres = findMax(root.left);
  let rres = findMax(root.right);
  
  if (lres > res) res = lres;
  if (rres > res) res = rres;
  
  return res;
}

Time Complexity: O(N). In the recursive function calls, every node of the tree is processed once. Space Complexity: O(N) considering the recursive stack space.

5. Size of Binary Tree

Size of a tree is the number of elements present in the tree.

Approach: A size() function can recursively calculate the size of a tree. It works as follows: Size of a tree = Size of left subtree + 1 + Size of right subtree

Algorithm:

If tree is empty then return 0
Else:
- Get the size of left subtree recursively
- Get the size of right subtree recursively
- Calculate size of the tree as: tree_size = size(left-subtree) + size(right-subtree) + 1
- Return tree_size

function getSize(root) {
  if (root === null) return 0;
  return getSize(root.left) + 1 + getSize(root.right);
}

Time Complexity: O(N) as every node is visited once. Auxiliary Space: O(N). The extra space is due to the recursion call stack and the worst case occurs when the tree is either left skewed or right skewed.

Deque (Double Ended Queue)Binary Search Tree