Mercer-Lee's Space
Search K

English

简体中文

English

简体中文

Appearance

Basic Concepts of Trees ​

A tree is an abstract model of hierarchical data. A tree structure consists of a series of nodes with parent-child relationships. Each node has one parent node (except the first node at the top, called the root) and zero or more child nodes.

tree1

In the tree above, "root" is the root node, and c, d, e, f are leaf nodes — nodes with no children.

The depth of this tree is 2. Depth is determined by the number of ancestor nodes. Node c has two ancestor nodes, so its depth is 2.

The height of the tree is the maximum depth among all nodes, which is 2.

These are the basic concepts of trees. Next, we'll discuss binary trees and binary search trees.

Binary Trees and Binary Search Trees (BST) ​

A binary tree differs from a regular tree in that each node can have at most two child nodes: a left child and a right child.

A Binary Search Tree (BST) is a type of binary tree where values smaller than the parent node are stored on the left, and values larger than the parent node are stored on the right. As shown:

BST

Code Implementation ​

First, let's create a node class:

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

// Comparison helper function
function defaultCompare(a, b) {
  if (a === b) {
    return 0;
  }
  return a < b ? -1 : 1;
}

The left and right properties act like pointers — they point to other Node instances. Now let's implement the BST:

javascript
class BinarySearchTree{
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;   // Comparison method
    this.root = undefined;    // Root node
  }
}

Insert ​

javascript
insert(key) {
  if (this.root == null) {
    this.root = new Node(key);    // If no root exists, initialize it
  } else {
    this.insertNode(this.root, key);
  }
}

insertNode(node, key) {
  if (this.compareFn(key, node.key) === -1) {   // Check if smaller than current node
    if (node.left == null) {    // If no left child, create one; otherwise recurse left
      node.left = new Node(key);
    } else {
      this.insertNode(node.left, key);
    }
  } else if (node.right == null) {    // Same logic for right child
    node.right = new Node(key);
  } else {
    this.insertNode(node.right, key);
  }
}

To search for a value in a BST, we need a search method:

javascript
search(key) {
    return this.searchNode(this.root, key);
  }
searchNode(node, key) {
  if (node == null) {   // If node is null, return false
    return false;
  }
  if (this.compareFn(key, node.key) === -1) {   // If smaller, recurse left
    return this.searchNode(node.left, key);
  } else if (this.compareFn(key, node.key) === 1) {   // If larger, recurse right
    return this.searchNode(node.right, key);
  }
  return true;  // Found it
}

Minimum Value ​

To find the minimum value in the tree:

javascript
min() {
  return this.minNode(this.root);
}
minNode(node) {
  let current = node;
  while (current != null && current.left != null) {   // Keep going left
    current = current.left;
  }
  return current;
}

Maximum Value ​

To find the maximum value in the tree:

javascript
max() {
  return this.maxNode(this.root);
}
maxNode(node) {
  let current = node;
  while (current != null && current.right != null) {   // Keep going right
    current = current.right;
  }
  return current;
}

Remove ​

Removing a node from a BST is complex. The logic isn't hard, but the code is intricate:

javascript
remove(key){
  this.root = this.removeNode(this.root, key);
}

removeNode(node, key) {
  if (node == null) {
    return undefined;
  }
  // If key is smaller, recurse left
  if (this.compareFn(key, node.key) === -1) {
    node.left = this.removeNode(node.left, key);
    return node;
  // If key is larger, recurse right
  } else if (this.compareFn(key, node.key) === 1) {
    node.right = this.removeNode(node.right, key);
    return node;
  }
  // Case 1: Leaf node (no children) — simply remove it
  if (node.left == null && node.right == null) {
    node = undefined;
    return node;
  }
  // Case 2: One child — replace node with its child
  if (node.left == null) {
    node = node.right;
    return node;
  } else if (node.right == null) {
    node = node.left;
    return node;
  }
  // Case 3: Two children — find the minimum node in the right subtree
  const aux = this.minNode(node.right);
  node.key = aux.key;
  // Recursively remove the minimum node from right subtree (it might have children)
  node.right = this.removeNode(node.right, aux.key);
  return node;
}

Summary ​

That's the complete JavaScript implementation of a BST. Everything is fairly straightforward except for the remove method, which is the trickiest part.