Implementing Custom BSTs with Classes and Comparators in JavaScript

Topic Overview

Welcome to our exploration of sorted maps using custom classes and comparators in JavaScript. In today's lesson, we'll learn how to use custom classes as keys in sorted maps. This approach enhances data organization and access. Since JavaScript does not have direct support for sorted maps, we'll use a Binary Search Tree (BST) to achieve this functionality by leveraging the @datastructures-js/binary-search-tree library.

Introduction to Custom Classes in JavaScript

Custom classes enable us to create objects that fit our data — for instance, a Person class for employee information or a Book class for a library database. In JavaScript, classes are the blueprints for creating objects. Consider this simple class, for example: JavaScript class Person {constructor(name, age) {this.name = name; this.age = age;}} let person = new Person("John Doe", 30); console.log(person.name); // Outputs "John Doe" console.log(person.age); // Outputs 30

Using Custom Classes with Binary Search Trees

Using custom classes helps organize complex multivariate data. We will use the @datastructures-js/binary-search-tree library to maintain our data in a sorted order. Below is an example of how to use comparators to dictate the order when using custom classes with this binary search tree: JavaScript const { BinarySearchTree } = require('@datastructures-js/binary-search-tree'); class Person {constructor(name, age, occupation) {this.name = name; this.age = age; this.occupation = occupation;} compare(other) {return this.age - other.age;} toString() {return `${this.name} is a ${this.occupation}`;}} let tree = new BinarySearchTree((a, b) => a.compare(b)); let john = new Person("John", 30, "Programmer"); let alice = new Person("Alice", 25, "Designer"); tree.insert(john); tree.insert(alice); // In-order traversal to print sorted entries tree.traverseInOrder((person) => {console.log(person.getValue().toString());}); // Output: // Alice is a Designer // John is a Programmer In-order traversal is a method of traversing a binary search tree where nodes are visited in ascending order. This means visiting the left subtree first, then the current node, and finally the right subtree. This ensures that data is accessed sequentially, from the smallest to the largest value.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

JavaScript

const { BinarySearchTree } = require('@datastructures-js/binary-search-tree');

class Person {
    constructor(name, age, occupation) {
        this.name = name;
        this.age = age;
        this.occupation = occupation;
    }

    compare(other) {
        return this.age - other.age;
    }

    toString() {
        return `${this.name} is a ${this.occupation}`;
    }
}

let tree = new BinarySearchTree((a, b) => a.compare(b));

let john = new Person("John", 30, "Programmer");
let alice = new Person("Alice", 25, "Designer");

tree.insert(john);
tree.insert(alice);

// In-order traversal to print sorted entries
tree.traverseInOrder((person) => {
    console.log(person.getValue().toString());
});
// Output:
// Alice is a Designer
// John is a Programmer

JavaScript

const { BinarySearchTree } = require('@datastructures-js/binary-search-tree');

class Person {
    constructor(name, age, occupation) {
        this.name = name;
        this.age = age;
        this.occupation = occupation;
    }

    compare(other) {
        // Different comparator: prioritize by occupation first, then by name
        if (this.occupation === other.occupation) {
            return this.name.localeCompare(other.name);
        }
        return this.occupation.localeCompare(other.occupation);
    }

    toString() {
        return `${this.name} is a ${this.occupation}`;
    }
}

let tree = new BinarySearchTree((a, b) => a.compare(b));

let john = new Person("John", 30, "Programmer");
let alice = new Person("Alice", 25, "Designer");
let bob = new Person("Bob", 27, "Programmer");

tree.insert(john);
tree.insert(alice);
tree.insert(bob);

// In-order traversal to print sorted entries
tree.traverseInOrder((person) => {
    console.log(person.getValue().toString());
});
// Output:
// Alice is a Designer
// Bob is a Programmer
// John is a Programmer

JavaScript

const { BinarySearchTree } = require('@datastructures-js/binary-search-tree');

class Person {
    constructor(name, age, occupation) {
        this.name = name;
        this.age = age;
        this.occupation = occupation;
    }

    compare(other) {
        // Different comparator: prioritize by occupation first, then by name
        if (this.occupation === other.occupation) {
            return this.name.localeCompare(other.name);
        }
        return this.occupation.localeCompare(other.occupation);
    }

    toString() {
        return `${this.name} is a ${this.occupation}`;
    }
}

let tree = new BinarySearchTree((a, b) => a.compare(b));

let john = new Person("John", 30, "Programmer");
let alice = new Person("Alice", 25, "Designer");
let bob = new Person("Bob", 27, "Programmer");

tree.insert(john);
tree.insert(alice);
tree.insert(bob);

// In-order traversal to print sorted entries
tree.traverseInOrder((person) => {
    console.log(person.getValue().toString());
});
// Output:
// Alice is a Designer
// Bob is a Programmer
// John is a Programmer

Topic Overview

Introduction to Custom Classes in JavaScript

Using Custom Classes with Binary Search Trees

Join the 1M+ learners on CodeSignal

Comparators and Their Role in Binary Search Trees

Lesson Summary and Practice