Binary tree

Binary trees are a fundamental data structure in computer science used to represent hierarchical relationships. They consist of nodes connected by edges and have a wide range of applications, from representing file systems to organizing data for efficient searching and sorting. By today we're here to talk about their simplest version binary tree

Theory

A binary tree is a tree with two main rules to follow:

• each node has at most two children, referred to as the left and right child.
• each node in the left subtree is less than the node's value, and the value of all nodes in the right subtree is greater than the node's value.

Implementation

Node Class

The Node class represents each element in the binary tree. Each node has a value and pointers to its left and right children.

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

Explanation: Each node has a value property to store data as well as a left and right property representing pointers to the node's left and right children, respectively.

Binary Search Tree Class

The BinarySearchTree class has only one property, the root node set to null by default.

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

Insert

The insert method adds a new node to the binary search tree. It ensures that the new node is placed in the correct position based on its value.

function insert(value) {
  const newNode = new Node(value);
  if (this.root === null) {
    this.root = newNode;
    return this;
  }
  let current = this.root;
  while (true) {
    if (value === current.value) return undefined;
    if (value < current.value) {
      if (current.left === null) {
        current.left = newNode;
        return this;
      }
      current = current.left;
    } else {
      if (current.right === null) {
        current.right = newNode;
        return this;
      }
      current = current.right;
    }
  }
}

Explanation:

• A new Node is created with the given value.
• If the tree is empty we only need to set the new node to be the root.
• Otherwise, we start from the root and traverse the tree until reaching one of those cases:
  • If the value is equal to the current node's value, return undefined (no duplicates allowed).
  • If the value is less than the current node's value, move to the left child, check if its left child is null (meaning there's a place to fill), then insert the new node there otherwise move to the left child.
  • If the value is greater than the current node's value, move to the right child, check if the right child is null (meaning there's a place to fill), then insert the new node there otherwise move to the right child.

Find

The find method searches for a node with a specific value and returns the node if found. It traverses the tree starting from the root, comparing the target value with the current node's value to decide which subtree to traverse.

function find(value) {
  if (this.root === null) return false;
  let current = this.root;
  let found = false;
  while (current && !found) {
    if (value < current.value) {
      current = current.left;
    } else if (value > current.value) {
      current = current.right;
    } else {
      found = true;
    }
  }
  if (!found) return undefined;
  return current;
}

Explanation:

Here again we have a few cases to handle:

• If the tree is empty (this.root === null), return false.
• Otherwise start from the root and traverse the tree:
  • If the value is less than the current node's value, move to the left child.
  • If the value is greater than the current node's value, move to the right child.
  • If the value is equal to the current node's value, set found to true to stop the loop and return the value.

After the loop we basically have two possibilities:

• If the value is not found, return undefined.
• If the value is found, return the node.

Contains

The contains method checks if a value exists in the tree. It is similar to the find method but returns a boolean value indicating the presence of the value.

function contains(value) {
  if (this.root === null) return false;
  let current = this.root;
  while (current) {
    if (value < current.value) {
      current = current.left;
    } else if (value > current.value) {
      current = current.right;
    } else {
      return true;
    }
  }

  return false;
}

Explanation:

Same here we have a few cases to handle:

• If the tree is empty, simply return false.
• Otherwise, start from the root and traverse the tree until matching one of those cases:
  • If the value is less than the current node's value, move to the left child.
  • If the value is greater than the current node's value, move to the right child.
  • If the value is equal to the current node's value, return true.

If we reach the end of the loop it means the value could not be found, so return false.

Remove

The remove method deletes a node with a specific value from the tree. We have three cases to handle, removing a leaf node, removing a node with one child, and removing a node with two children.

function remove(val) {
  if (!this.root) return null;
  let node = this.root;
  if (node.value === val) {
    if (node.left === null && node.right === null) {
      this.root = null;
      return node;
    } else if (node.left !== null && node.right !== null) {
      let right = node.right;
      if (right.left === null) {
        right.left = node.left;
        this.root = right;
      } else {
        let rightParent = node;
        while (right.left !== null) {
          rightParent = right;
          right = right.left;
        }
        rightParent.left = right.right;
        right.left = node.left;
        right.right = node.right;
        this.root = right;
      }
      return node;
    } else {
      this.root = node.left || node.right;
      return node;
    }
  }


  let parentNode;
  while (node.value !== val) {
    parentNode = node;
    if (node.value > val) {
      node = node.left;
    } else {
      node = node.right;
    }
  }

  if (node !== this.root) {
    if (node.left === null && node.right === null) {
      if (parentNode.left === node) {
        parentNode.left = null;
      } else {
        parentNode.right = null;
      }
    } else if (node.left !== null && node.right !== null) {
      let rightParent = node;
      let right = node.right;
      if (right.left === null) {
        right.left = node.left;
        if (parentNode.left === node) {
          parentNode.left = right;
        } else {
          parentNode.right = right;
        }
      } else {
        while (right.left !== null) {
          rightParent = right;
          right = right.left;
        }
        if (parentNode.left === node) {
          parentNode.left.value = right.value;
        } else {
          parentNode.right.value = right.value;
        }
        if (right.right !== null) {
          rightParent.left = right.right;
        } else {
          rightParent.left = null;
        }
      }
    } else {
      if (parentNode.left === node) {
        if (node.right === null) {
          parentNode.left = node.left;
        } else {
          parentNode.left = node.right;
        }
      } else {
        if (node.right === null) {
          parentNode.right = node.left;
        } else {
          parentNode.right = node.right;
        }
      }
    }
  }

  return node;
}

Explanation:

We essentially have three cases to handle:

• Leaf Node Removal: When the node to be removed has no children, it simply removes the reference from its parent.
• Node with Two Children: When the node to be removed has two children, it finds the in-order successor (leftmost node in the right subtree) to replace the node to be removed. This ensures that the BST properties are maintained.
• Node with One Child: When the node to be removed has only one child, it bypasses the node to be removed by making its parent point directly to its child.

It ensures that after removal, the tree remains a valid binary search tree where for any given node:

• All values in its left subtree are less than its value
• All values in its right subtree are greater than its value

IsBalanced

The isBalanced method checks if the tree is balanced meaning the height difference between the left and right subtrees of every node is not more than 1.

function isBalanced(node = this.root) {
  if (!node) {
    return true;
  }
  return getHeightDiff(node) !== -1;

  function getHeightDiff(node) {
    if (node === null) return 0;
    const leftHeight = getHeightDiff(node.left);
    if (leftHeight === -1) return -1;
    const rightHeight = getHeightDiff(node.right);
    if (rightHeight === -1) return -1;
    if (Math.abs(leftHeight - rightHeight) > 1) {
      return -1;
    } else {
      return Math.max(leftHeight, rightHeight) + 1;
    }
  }
}

Explanation:

Here we are recursively checking if the tree is balanced and for that we choose the inner function pattern which to me allows for more clarity.

• Our outer function isBalanced first check if the node is empty, if so we return true
• Otherwise we execute the recursive function getHeightDiff and return a boolean based on the height diff
• The getHeightDiff function recursively calculates the height difference between the left and right subtrees, from there we have a few cases to handle:
  • If the node is null, return 0;
  • Recursively calculate the height of the left subtree. If the left subtree is not balanced (leftHeight === -1), return -1.
  • Recursively calculate the height of the right subtree. If the right subtree is not balanced (rightHeight === -1), return -1.
  • If the absolute difference between the left and right subtree heights is greater than 1, it means our tree is not balanced, so return -1.
  • Otherwise, return the height of the current node, which is the maximum height between its subtrees plus 1.
• If getHeightDiff returns -1, it means our tree is not balanced, so isBalanced returns false. Otherwise, we return true.

Tree Traversal

Traversing a tree involves visiting each node in a specific order. There are two main approaches: Depth First Search (DFS) and Breadth First Search (BFS).

Depth First Search (DFS)

DFS involves traversing as deep as possible along each branch before backtracking. From there, there are three resulting orders:

PreOrder

Push the current node, then it's left property, then it's right property until reaching the up most right leaf.

function DFSPreOrder() {
  let result = [];
  function traverse(node) {
    result.push(node.value);
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
  }
  traverse(this.root);
  return result;
}

Explanation:

• Create an empty array result to store the traversal order.
• Define a nested traverse function that takes a node as an argument.
• Push the node's value to result.
• Recursively call traverse on the left child if it exists.
• Recursively call traverse on the right child if it exists.
• Call traverse with the root node to start the traversal.
• Return the result array.

InOrder

Visit the left subtree, push the current node, then visit the right subtree.

function DFSInOrder() {
  let result = [];
  function traverse(node) {
    if (node.left) traverse(node.left);
    result.push(node.value);
    if (node.right) traverse(node.right);
  }
  traverse(this.root);
  return result;
}

Explanation: Similar to DFSPreOrder, but the node's value is pushed to result after traversing the left subtree and before traversing the right subtree.

PostOrder

Visit the left subtree, then the right subtree, then push the current node.

function DFSPostOrder() {
  let result = [];
  function traverse(node) {
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
    result.push(node.value);
  }
  traverse(this.root);
  return result;
}

Explanation: Similar to DFSInOrder, but the node's value is pushed to result after traversing both the left and right subtrees.

Breadth First Search (BFS)

BFS involves visiting all nodes at the present depth before moving on to the next depth level. We use a queue to keep track of the nodes to visit.

function BFS() {
  let node = this.root;
  let result = [];
  let queue = [];
  queue.push(node);
  while (queue.length) {
    node = queue.shift();
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

Explanation:

• Create an empty array result to store the traversal order.
• Create an empty array queue to keep track of nodes to visit.
• Push the root node to queue to start the traversal.
• As long as queue has nodes:
  • Dequeue the first node and assign it to node.
  • Push the node's value to result.
  • Enqueue the left child of node if it exists.
  • Enqueue the right child of node if it exists.
• Return the result array.

Performance Considerations

• Time Complexity: For insertion, deletion, and search operations, the average time complexity is O(log n) for a balanced BST. However, in the worst case (unbalanced tree), it can degrade to O(n).
• Space Complexity: The space complexity for traversal methods is O(n) due to the storage required for the result array and the call stack or queue.

Practical Use Cases

Binary trees are used in various applications, including:

• Database indexing: BSTs are used to index databases for efficient searching.
• File systems: Trees are used to represent the hierarchical structure of file systems.
• Compiler design (syntax trees): Trees are used to represent the syntactic structure of source code.
• Network routing algorithms: Trees are used to represent network topologies and routing paths.

Conclusion

Congratulations 🎉! You made it through! I hope you learned a lot about binary trees and their implementation in JavaScript. If you have any suggestions, improvements, or questions, don't hesitate to write. I'll reply as soon as possible!

Happy coding!