Tree Definiiton and Characteristics

A tree is a data structure with n (n ≥ 0) finite nodes in a hierarchical relationship. Called a "tree" as it resembles an upside - down tree (root up, leaves down). Key traits:

• A node may have 0+ child nodes.
• The root node has no parent.
• Every non - root node has exactly one parent.
• Except the root, each child node can belong to multiple disjoint subtrees.
• A binary tree allows at most two subtrees per node.
• A Binary Search Tree (BST) (also named ordered/sorted binary tree) is a binary tree (or empty) with:
  • If the left subtree is not empty, all left - subtree nodes have values less than the root’s value.
  • If the right subtree is not empty, all right - subtree nodes have values greater than the root’s value.

Code Implementation

Main Class (Binary Search Tree)

class BinaryTree {
  constructor() {
    this.root = null; // Renamed for clarity
  }
}

Node Class (Linked - List - like Structure)

class TreeNode {
  constructor(value) {
    this.value = value; // Renamed from 'key'
    this.leftChild = null; // Renamed from 'left'
    this.rightChild = null; // Renamed from 'right'
  }
}

Inserting Nodes

// Add a node to the tree
BinaryTree.prototype.add = function (value) {
  const newNode = new TreeNode(value);
  if (this.root === null) {
    this.root = newNode;
  } else {
    insertIntoTree(this.root, newNode);
  }
};

function insertIntoTree(currentRoot, newNode) {
  if (newNode.value < currentRoot.value) {
    if (currentRoot.leftChild === null) {
      currentRoot.leftChild = newNode;
    } else {
      insertIntoTree(currentRoot.leftChild, newNode);
    }
  } else {
    if (currentRoot.rightChild === null) {
      currentRoot.rightChild = newNode;
    } else {
      insertIntoTree(currentRoot.rightChild, newNode);
    }
  }
}

Tree Traversal

Three common traversal methods (recursive implementations; iterative versions exist too):

// Pre - order: Root → Left Subtree → Right Subtree
BinaryTree.prototype.preOrderTraverse = function (callback) {
  preOrderHelper(this.root, callback);
};

function preOrderHelper(node, callback) {
  if (node) {
    callback(node.value);
    preOrderHelper(node.leftChild, callback);
    preOrderHelper(node.rightChild, callback);
  }
}

// In - order: Left Subtree → Root → Right Subtree
BinaryTree.prototype.inOrderTraverse = function (callback) {
  inOrderHelper(this.root, callback);
};

function inOrderHelper(node, callback) {
  if (node) {
    inOrderHelper(node.leftChild, callback);
    callback(node.value);
    inOrderHelper(node.rightChild, callback);
  }
}

// Post - order: Left Subtree → Right Subtree → Root
BinaryTree.prototype.postOrderTraverse = function (callback) {
  postOrderHelper(this.root, callback);
};

function postOrderHelper(node, callback) {
  if (node) {
    postOrderHelper(node.leftChild, callback);
    postOrderHelper(node.rightChild, callback);
    callback(node.value);
  }
}

Min/Max Values

To find the leftmost (min) or rightmost (max) node:

// Find minimum value (leftmost node)
BinaryTree.prototype.findMin = function () {
  if (!this.root) return null;
  return getMinNode(this.root).value;
};

// Find maximum value (rightmost node)
BinaryTree.prototype.findMax = function () {
  if (!this.root) return null;
  return getMaxNode(this.root).value;
};

function getMinNode(node) {
  while (node && node.leftChild) {
    node = node.leftChild;
  }
  return node;
}

function getMaxNode(node) {
  while (node && node.rightChild) {
    node = node.rightChild;
  }
  return node;
}

Search for a Value

Check if a value exists in the tree:

BinaryTree.prototype.contains = function (target) {
  return searchTree(this.root, target);
};

function searchTree(node, target) {
  if (!node) return false;
  if (target === node.value) {
    return true;
  } else if (target < node.value) {
    return searchTree(node.leftChild, target);
  } else {
    return searchTree(node.rightChild, target);
  }
}

Remove a Node

Removing a node has three cases (no children, one child, two children; replace with in - order successor for two children):

BinaryTree.prototype.remove = function (value) {
  this.root = removeTreeNode(this.root, value);
};

function removeTreeNode(node, value) {
  if (!node) return null;

  if (value < node.value) {
    node.leftChild = removeTreeNode(node.leftChild, value);
    return node;
  } else if (value > node.value) {
    node.rightChild = removeTreeNode(node.rightChild, value);
    return node;
  } else {
    // Case 1: No children
    if (!node.leftChild && !node.rightChild) {
      node = null;
      return node;
    }

    // Case 2: One child
    if (!node.leftChild) {
      node = node.rightChild;
      return node;
    } else if (!node.rightChild) {
      node = node.leftChild;
      return node;
    }

    // Case 3: Two children
    const successor = getMinNode(node.rightChild);
    node.value = successor.value;
    node.rightChild = removeTreeNode(node.rightChild, successor.value);
    return node;
  }
}

Code Testing

const bst = new BinaryTree();
bst.add(11);
bst.add(7);
bst.add(15);
bst.add(5);
bst.add(3);
bst.add(9);
bst.add(8);
bst.add(10);
bst.add(13);
bst.add(12);
bst.add(14);
bst.add(20);
bst.add(25);
bst.add(6);
bst.add(18);

// Pre - order traversal test
let preOrderResult = "";
bst.preOrderTraverse((val) => {
  preOrderResult += val + " ";
});
console.log("Pre - order:", preOrderResult.trim());

// In - order traversal test
let inOrderResult = "";
bst.inOrderTraverse((val) => {
  inOrderResult += val + " ";
});
console.log("In - order:", inOrderResult.trim());

// Min value test
const minVal = bst.findMin();
console.log("Minimum value:", minVal);

// Max value test
const maxVal = bst.findMax();
console.log("Maximum value:", maxVal);

// Search test
const hasEight = bst.contains(8);
console.log("Contains 8:", hasEight);

// Remove test
bst.remove(15);
let updatedInOrder = "";
bst.inOrderTraverse((val) => {
  updatedInOrder += val + " ";
});
console.log("After removing 15 (in - order):", updatedInOrder.trim());