BST

by Steven Senkus

JavaScript

/**
 * @fileoverview Binary Search Tree implementation in JavaScript
 */

/*
 * These symbols are used to represent properties that should not be part of
 * the public interface. You could also use ES2019 private fields, but those
 * are not yet widely available as of the time of my writing.
 */
const root = Symbol("root");

/**
 * Represents a single node in a BinarySearchTree.
 * @class BinarySearchTree
 */
class BinarySearchTreeNode {

    /**
     * Creates a new instance of BinarySearchTreeNode.
     * @param {*} value The value to store in the node. 
     */
    constructor(value) {

        /**
         * The value that this node stores.
         * @property value
         * @type *
         */
        this.value = value;

        /**
         * A pointer to the left node in the BinarySearchTree.
         * @property left
         * @type ?BinarySearchTreeNode
         */
        this.left = null;

        /**
         * A pointer to the right node in the BinarySearchTree.
         * @property right
         * @type ?BinarySearchTreeNode
         */
        this.right = null;

    }
}

/**
 * A linked tree implementation in JavaScript.
 * @class BinarySearchTree
 */
class BinarySearchTree {

    /**
     * Creates a new instance of BinarySearchTree
     */
    constructor() {

        /**
         * Pointer to the root node in the tree.
         * @property root
         * @type ?BinarySearchTreeNode
         * @private
         */
        this[root] = null;
    }
    
    /**
     * Adds some value into the tree. This method traverses the tree to find
     * the correct location to insert the value. Duplicate values are discarded.
     * @param {*} value The value to add to the tree.
     * @returns {void}
     */
    add(value) {
    
        /*
         * Create a new node to insert into the tree and store the value in it.
         * This node will be added into the tree.
         */
        const newNode = new BinarySearchTreeNode(value);

        //...