Binary Tree

In this chapter you will learn the basics of binary tree it's implementation and different applications.

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. The root of a binary tree is the topmost node. Each node in a binary tree can have at most two children. A node can have zero children, one child, or two children.

Types of Binary Trees

• Full Binary Tree. A binary tree is full if every node has 0 or 2 children.
• Complete Binary Tree. A binary tree is complete if all levels are completely filled except possibly for the last level, which is filled from left to right.
• Perfect Binary Tree. A binary tree is perfect if all internal nodes have two children and all leaves are at the same level.
• Balanced Binary Tree. A binary tree is balanced if the height of the tree is O(log n) where n is the number of nodes.

Binary Tree Applications

Binary trees are used in a variety of applications, including:

• Binary Search Tree. A binary search tree is a binary tree in which the left child of a node contains only nodes with keys less than the node's key, and the right child only nodes with keys greater than the node's key.
• Expression Tree. An expression tree is a binary tree in which each internal node represents an operator and each leaf node represents an operand.
• Huffman coding tree. A Huffman coding tree is a binary tree used for data compression.
• Binary Heap. A binary heap is a binary tree that satisfies the heap property.

Operations on a Binary Tree

The most common operations on a binary tree include:

• Inserting a new node into the tree.
• Removing a node from the tree.
• Visiting all the nodes in the tree in a specific order.
• Finding a specific node in the tree.

Implementation

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

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

  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    this.insertNode(this.root, newNode);
  }

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

  inOrderTraversal(node = this.root) {
    if (node !== null) {
      this.inOrderTraversal(node.left);
      console.log(node.value);
      this.inOrderTraversal(node.right);
    }
  }

  search(value, node = this.root) {
    if (node === null) {
      return false;
    }
    if (value < node.value) {
      return this.search(value, node.left);
    } else if (value > node.value) {
      return this.search(value, node.right);
    } else {
      return true;
    }
  }
}

Example of usage:

// Usage example
const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

console.log("In-order traversal:");
tree.inOrderTraversal();

console.log("Search for 7:", tree.search(7));
console.log("Search for 100:", tree.search(100));

Complexity Analysis

• Insert operation takes O(log N) of time complexity and O(1) of space complexity in average.
• Search operation takes O(log N) of time complexity and O(1) of space complexity in average.
• Traversals (In-order, Pre-order, Post-order) takes in average case O(n) of time complexity and O(log N) of space complexity.