Data Structure and Algorithms with JS - Part 4 : Tree

April 16, 2022 • 27 min read

DSA

JavaScript

Tree

A tree is a non-linear data structure that represents a hierarchical relationship between nodes. Each node in a tree has a value and can have zero or more child nodes, which are connected to it via edges. The node at the top of the tree is called the root node, and the nodes that do not have any children are called leaf nodes.

The tree data structure is often used to represent hierarchical relationships in data, such as the structure of a file system, the structure of an organization, or the structure of a decision-making process.

Some common terminologies used in the context of tree data structure:

Root: The root of a tree is the topmost node in the tree. It is the ancestor of all other nodes in the tree.
Child: A child of a node is a node that is directly connected to it via an edge. A node can have zero or more children, depending on the structure of the tree.
Parent: A parent of a node is a node that is directly connected to it via an edge. Every node in a tree, except for the root, has a parent.
Leaf: A leaf is a node that does not have any children. Leaf nodes are the terminal nodes of a tree.
Subtree: A subtree of a tree is a portion of the tree that includes a node and all of its descendants.
Ancestor: An ancestor of a node is a node that is located above it in the tree and can be reached by traversing the tree upwards from the node. The root of the tree is an ancestor of every node in the tree.
Descendant: A descendant of a node is a node that is located below it in the tree and can be reached by traversing the tree downwards from the node. Every node in the tree is a descendant of the root.
Sibling: Siblings are nodes that have the same parent.
Degree: The degree of a node is the number of children it has.
Height: The height of a tree is the number of edges on the longest downward path between the root and a leaf. The height of a node is the number of edges on the longest downward path between the node and a leaf.
Depth: The depth of a node is the number of edges on the path from the root to the node.
Level: The level of a node is the number of ancestors it has. The root of the tree is at level 0, and the children of the root are at level 1, and so on.
Path: A path in a tree is a sequence of nodes connected by edges.
Traversal: Traversal refers to the process of visiting and processing the nodes of a tree in a specific order. There are various tree traversal algorithms, including

Some characteristics of the tree data structure:

Hierarchical structure:

Trees have a hierarchical structure, with the root node at the top and the leaf nodes at the bottom. This structure allows for the representation of complex relationships between nodes.

Recursive structure:

Trees have a recursive structure, with each node potentially having its own sub-tree of child nodes. This allows for the representation of an unbounded number of nodes within a tree.

Non-linear:

Trees are a non-linear data structure, meaning that the nodes in a tree are not stored in a contiguous block of memory like an array. Instead, each node is stored separately and is connected to other nodes via edges.

Efficient search:

Trees can be used to efficiently search for specific values within a dataset. For example, binary search trees allow for efficient search operations by exploiting the hierarchical structure of the tree.

Efficient insertion and deletion:

Trees can be used to efficiently insert and delete elements, particularly if the tree is balanced.

Flexible structure: Trees have a flexible structure, which allows them to adapt to changing data and changing requirements. For example we can have any number of child nodes to fit our requirements.

There are several types of tree data structures, each with its own characteristics and use cases:

N-ary tree:

Trees can have more than two children per node, in which case they are called n-ary trees.

Binary tree:

A binary tree is a tree data structure in which each node has at most two children. Binary trees are commonly used to implement search algorithms, such as binary search. Read More…

Binary search tree:

A binary search tree is a binary tree in which the value of each node is greater than the values of its left children and less than the values of its right children. Binary search trees are used to efficiently search for specific values within a dataset. Read More…

Balanced tree:

A balanced tree is a tree data structure in which the heights of the left and right subtrees of each node differ by at most 1. Balanced trees are used to maintain efficient search and insertion/deletion operations. Read More…

Heap:

A heap is a tree data structure that satisfies the heap property, which states that the value of each node is greater than or equal to the values of its children (in a max-heap) or less than or equal to the values of its children (in a min-heap). Heaps are used to implement efficient priority queues and sorting algorithms.

A max-heap is a complete binary tree in which the value of each node is greater than or equal to the values of its children. The root node of a max-heap is the maximum element in the heap.

A min-heap is a complete binary tree in which the value of each node is less than or equal to the values of its children. The root node of a min-heap is the minimum element in the heap. Read More…

Trie:

A trie (also known as a prefix tree) is a tree data structure used to store a dynamic set or associative array where the keys are sequences (usually strings). Tries are used for efficient prefix-based search, such as for spelling correction or for efficient data retrieval in databases. Read More…

Splay tree:

A splay tree is a self-balancing binary search tree that rearranges itself after each search operation to bring the searched-for item closer to the root. Splay trees are used to implement efficient data structures for dynamic sets and associative arrays. Read More…

Red-black tree:

A red-black tree is a self-balancing binary search tree that maintains a specific coloring scheme (red and black) in order to balance the tree. Red-black trees are used to implement efficient data structures for dynamic sets and associative arrays. Read More…

AVL tree:

An AVL tree is a self-balancing binary search tree that maintains balance by enforcing a height difference constraint between the left and right subtrees of each node. AVL trees are used to implement efficient data structures for dynamic sets and associative arrays. Read More…

Binary Search Tree Implementation using JavaScript

class TreeNode {
  constructor(value) {
    this.left = null
    this.right = null
    this.value = value
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null
  }

  insert(value) {
    let newNode = new TreeNode(value)
    if (!this.root) {
      this.root = newNode
      return
    }
    let curr = this.root
    while (curr) {
      if (value <= curr.value) {
        if (curr.left) {
          curr = curr.left
        } else {
          curr.left = newNode
          break
        }
      } else {
        if (curr.right) {
          curr = curr.right
        } else {
          curr.right = newNode
          break
        }
      }
    }
  }
  lookup(value) {
    if (!this.root) return "Empty Array"
    let curr = this.root
    while (curr) {
      if (value === curr.value) {
        return curr
      } else if (value < curr.value) {
        curr = curr.left
      } else {
        curr = curr.right
      }
    }
    return "Not Found"
  }
  remove(value) {
    if (!this.root) return "Empty Array"
    let curr = this.root
    let parentNode = null
    while (curr) {
      if (value < curr.value) {
        parentNode = curr
        curr = curr.left
      } else if (value > curr.value) {
        parentNode = curr
        curr = curr.right
      } else {
        if (!curr.right) {
          if (!parentNode) {
            this.root = curr.left
          } else {
            if (curr.value < parentNode.value) {
              parentNode.left = curr.left
            } else if (curr.value > parentNode.value) {
              parentNode.right = curr.left
            }
          }
        } else if (!curr.right.left) {
          if (!parentNode) {
            this.root = curr.left
          } else {
            curr.right.left = curr.left
            if (curr.value < parentNode.value) {
              parentNode.left = curr.right
            } else if (curr.value > parentNode.value) {
              parentNode.right = curr.right
            }
          }
        } else {
          let leftmost = curr.right.left
          let leftmostParent = curr.right
          while (leftmost.left !== null) {
            leftmostParent = leftmost
            leftmost = leftmost.left
          }
          leftmostParent.left = leftmost.right
          leftmost.left = curr.left
          leftmost.right = curr.right
          if (!parentNode) {
            this.root = leftmost
          } else {
            if (curr.value < parentNode.value) {
              parentNode.left = leftmost
            } else {
              parentNode.right = leftmost
            }
          }
        }
      }
    }
  }
}

const tree = new BinarySearchTree()
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
console.log(tree.lookup(20))
/**
TreeNode {
  left: TreeNode { left: null, right: null, value: 15 },
  right: TreeNode { left: null, right: null, value: 170 },
  value: 20
}
 */
console.log(tree.lookup(150)) // Not Found
console.log(JSON.stringify(traverse(tree.root)))
/**
 * {"value":9,
 *  "left":{"value":4,"left":{"value":1,"left":null,"right":null}, "right":{"value":6,"left":null,"right":null}},
 *  "right":{"value":20,"left":{"value":15,"left":null,"right":null},"right":{"value":170,"left":null,"right":null}}}
 */

//     9
//  4     20
//1  6  15  170

function traverse(node) {
  const tree = { value: node.value }
  tree.left = node.left === null ? null : traverse(node.left)
  tree.right = node.right === null ? null : traverse(node.right)
  return tree
}

const maxDepth = function (root) {
  if (!root) return 0
  let maxDepth = 0
  const helper = (root, depth) => {
    if (root.left) helper(root.left, depth + 1)
    if (root.right) helper(root.right, depth + 1)
    if (!root.left) {
      if (depth > maxDepth) maxDepth = depth
      return
    }
    if (!root.right) {
      if (depth > maxDepth) maxDepth = depth
      return
    }
  }
  helper(root, 1)
  return maxDepth
}

Trees are a common data structure used in computer science to represent hierarchical relationships between objects.

Some common applications of tree data structures include:

Hierarchical data representation:

Tree data structures are often used to represent the hierarchical data structures, such as the hierarchy of files and directories in a file system or organizational structures. Each directory is represented as a node in the tree, with the files in that directory being the child nodes of the directory node.

Decision making:

Trees can be used to represent decision-making processes, such as in the game of chess where each move is represented as a node in the tree and the possible subsequent moves are the child nodes. The tree can be searched to find the best move based on a set of predetermined criteria.

Web navigation:

Trees can be used to represent the structure of a website, with the home page being the root node and the child nodes representing the pages linked from the home page. This can help with navigation and search functionality on a website.

Searching and sorting:

Trees can be used to implement efficient search and sorting algorithms, such as binary search trees and red-black trees to filter large amount or to find related keywords and results in a search engine.

Network routing:

Trees can be used to represent the topology of a network or network routing algorithms, with the nodes representing devices and the edges representing connections between the devices. This can help with routing data packets through the network.

Parsing:

Trees can be used to represent the structure of a mathematical expression, with the nodes representing the operators and the leaves representing the operands. This can be used to evaluate the expression or to simplify it. Other then this Trees are often used in natural language processing and computer science to represent the structure of a sentence or program.