Binary Trees

Node class

function Node(n, _left, _right) {
  this.value = n;
  this.left = _left ? _left : null;
  this.right = _right ? _right : null;
}

Function to create Binary Tree from Array

function Binary_Tree_From_Array(array, root, index = 0) {
    let lastIndex = (array.length >> 1) - 1;
    if (index > lastIndex) return;
    let left = (index << 1) + 1;
    let right = (index << 1) + 2;
    if (left < array.length)
      root.left = new Node(array[left]);
    if (right < array.length)
      root.right = new Node(array[right]);
    Binary_Tree_From_Array(array, root.left, (index << 1) + 1);
    Binary_Tree_From_Array(array, root.right, (index << 1) + 2);
}

Function to traverse Binary Tree

function Traverse(tree) {
  if (!tree) return;
  if (tree.left || tree.right)
      console.log("\nRoot: ", tree.value);
  else console.log("\nLeaf: ", tree.value);
  if (tree.left)
      console.log("Left: ", tree.left.value);
  if (tree.right)
      console.log("Right: ", tree.right.value);
  Traverse(tree.left);
  Traverse(tree.right);
}

Function to Heapify Binary Tree

function Heapify_Tree(tree, maxHeap = true) {
    if (!tree) return;
    Heapify_Tree(tree.left, maxHeap);
    Heapify_Tree(tree.right, maxHeap);
    
    // there are 3 possible cases:
    // tree is a leaf
    // tree has only one child (left)
    // tree has two children (left and right)
    if(maxHeap){
        if (tree.left && tree.left.value > tree.value) {
            let temp = tree.value;
            tree.value = tree.left.value;
            tree.left.value = temp;
            //console.log(`Swapped ${tree.value} with ${tree.left.value}`);
            Heapify_Tree(tree.left, maxHeap);
        }
        if (tree.right && tree.right.value > tree.value) {
            let temp = tree.value;
            tree.value = tree.right.value;
            tree.right.value = temp;
            //console.log(`Swapped ${tree.value} with ${tree.right.value}`);
            Heapify_Tree(tree.right, maxHeap);
        }
    }
    else{
        if (tree.left && tree.left.value < tree.value) {
            let temp = tree.value;
            tree.value = tree.left.value;
            tree.left.value = temp;
            //console.log(`Swapped ${tree.value} with ${tree.left.value}`);
            Heapify_Tree(tree.left, maxHeap);
        }
        if (tree.right && tree.right.value < tree.value) {
            let temp = tree.value;
            tree.value = tree.right.value;
            tree.right.value = temp;
            //console.log(`Swapped ${tree.value} with ${tree.right.value}`);
            Heapify_Tree(tree.right, maxHeap);
        }
    }
}

Properties of heap:

• Min heap: value of all nodes must be less than or equal to that of child nodes.
• Max heap: value of all nodes must be greater than or equal to that of child nodes.

Functions for Pre-order Post-order and In-order Traversal

function PreOrder(tree, array) {
  if (!tree) return;

  if (!array.includes(tree.value))
      array.push(tree.value);

  PreOrder(tree.left, array);
  PreOrder(tree.right, array);
}

function PostOrder(tree, array) {
  if (!tree) return;

  PostOrder(tree.left, array);
  PostOrder(tree.right, array);
  if (!array.includes(tree.value)) array.push(tree.value);
}

function InOrder(tree, array) {
  if (!tree) return;

  InOrder(tree.left, array);
  if (!array.includes(tree.value))
      array.push(tree.value);
  InOrder(tree.right, array);
}

Example to heapify binary tree

let arr = [5, 12, 64, 1, 37, 90, 91, 97];

let root1 = new Node(arr[0]),
    root2 = new Node(arr[0]);
Binary_Tree_From_Array(arr, root1);
Binary_Tree_From_Array(arr, root2);

console.log("Before Heapify");
Traverse(root1);

Heapify_Tree(root1);
console.log("\nAfter Max Heapify");
Traverse(root1);

Heapify_Tree(root2, false);
console.log("\nAfter Min Heapify");
Traverse(root2);

Before Heapify

Root:  5
Left:  12
Right:  64

Root:  12
Left:  1
Right:  37

Root:  1
Left:  97

Leaf:  97

Leaf:  37

Root:  64
Left:  90
Right:  91

Leaf:  90

Leaf:  91

After Max Heapify

Root:  97
Left:  37
Right:  91

Root:  37
Left:  5
Right:  12

Root:  5
Left:  1

Leaf:  1

Leaf:  12

Root:  91
Left:  64
Right:  90

Leaf:  64

Leaf:  90

After Min Heapify

Root:  1
Left:  5
Right:  64

Root:  5
Left:  12
Right:  37

Root:  12
Left:  97

Leaf:  97

Leaf:  37

Root:  64
Left:  90
Right:  91

Leaf:  90

Leaf:  91

---

Example of Tree Traversal

let arr2 = ["A", "B", "C", "D", "E"];

let root3 = new Node(arr2[0]);
Binary_Tree_From_Array(arr2, root3);
Traverse(root3);

let arr3 = [], arr4 = [], arr5 = [];
PreOrder(root3, arr3);
PostOrder(root3, arr4);
InOrder(root3, arr5);

console.log("\nPreOrder: ", arr3);
console.log("PostOrder: ", arr4);
console.log("InOrder: ", arr5);

Root:  A
Left:  B
Right:  C

Root:  B
Left:  D
Right:  E

Leaf:  D

Leaf:  E

Leaf:  C

PreOrder:  [ "A", "B", "D", "E", "C" ]
PostOrder:  [ "D", "E", "B", "C", "A" ]
InOrder:  [ "D", "B", "E", "A", "C" ]

---