Tree

A Tree is a non-linear data structure and a hierarchy 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.

Why is Tree 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.

Tree data structures are hierarchical data structures composed of nodes.

Each node has a value and a list of references to its child nodes.

Trees are commonly used to represent hierarchical data like file systems, organization charts, or even HTML DOM structures.

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

class BinaryTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
    } else {
      this._insertNode(this.root, newNode);
    }
  }

  _insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (!node.left) {
        node.left = newNode;
      } else {
        this._insertNode(node.left, newNode);
      }
    } else {
      if (!node.right) {
        node.right = newNode;
      } else {
        this._insertNode(node.right, newNode);
      }
    }
  }

  search(value) {
    return this._searchNode(this.root, value);
  }

  _searchNode(node, value) {
    if (!node) return false;
    if (node.value === value) return true;
    if (value < node.value) {
      return this._searchNode(node.left, value);
    } else {
      return this._searchNode(node.right, value);
    }
  }
}

// Example usage:
const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

console.log(tree.search(7)); // Output: true
console.log(tree.search(20)); // Output: false

In this example, TreeNode represents a single node in the binary tree, and BinaryTree represents the binary tree itself.

The insert method inserts a new value into the tree, maintaining the binary search tree property.

The search method searches for a value in the tree, returning true if found and false otherwise.

This is just a basic example of a tree data structure in JavaScript.

There are many other types of trees (e.g., binary search trees, AVL trees, red-black trees) and various operations you can perform on them.