Library Management System using Binary Search Tree (BST) [with source code]

In this article at OpenGenus.org, we will guide you through the creation of a Library Management System (LMS) using the Binary Search Tree (BST) data structure. Rather than an extensive introduction to BST, we will focus on practical implementation, starting with the system's requirements and features.

Table of Contents:

1. Requirements and Features
2. Approach: Leveraging Binary Search Trees
3. Implementation Details
4. Conclusion

See the full code: Github Repository

Requirements and Features

Before diving into the technical details, let's outline the requirements of our Library Management System and the features we aim to implement:

• Add a book to the library with a specified number of copies.
• Search for a book in the library.
• Lend a specified number of copies of a book.
• Return a specified number of copies of a book.
• Check the status of available copies for a book.
• Print the overall status of the library.
• User-friendly Command Line Interface (CLI) for interaction.

Approach: Leveraging Binary Search Trees

Our approach to implementing the Library Management System involves utilizing Binary Search Trees (BST). Here's why BST is a suitable choice:

Efficiency in Search Operations

BSTs offer swift search operations with a time complexity close to O(log n), making book retrieval quick and responsive. The ordered structure minimizes the search space at each step.

Natural Ordering of Books

BSTs inherently organize books in a sorted manner, simplifying tasks like adding books and presenting the library's status. The ordered arrangement aids in efficient in-order traversals, providing a sorted list of books.

BSTs adapt to dynamic changes in the library's collection, making them scalable. Their flexibility allows for easy extensions, accommodating additional attributes without compromising efficiency.

Implementation Details

Binary Search Tree in Node.js

Before making the application, we need to define the binary search tree and the methods (functions) that we are going to use beforehand. In this blog, we will focus on making the application with Node.js, chosen for its ease of use and widespread adoption.

Let's first create a binary search tree.

In a separate file binarySearchTree.js,

"use strict";

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

Here a Node class is defined to represent each node in the Binary Search Tree. Each node contains a key (book name) and the number of copies available. It also has references to its left and right children.

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

The BinarySearchTree class is the main class that will manage the binary search tree. It has a root property initialized to null initially.

  insert(key, copies = 1) {
    const newNode = new Node(key, copies);
    if (this.root === null) 
      this.root = newNode;
    else 
      this._insertNode(this.root, newNode);
  }

The insert method adds a new book to the library. If the tree is empty (root is null), it creates a new node and sets it as the root. Otherwise, it calls the private _insertNode method to recursively find the correct position for the new node, here if the copies isn't mentioned explicitly, it will take it as 1 copy.

  _insertNode(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null)
        node.left = newNode;
      else 
        this._insertNode(node.left, newNode);
    } 
    else if (newNode.key > node.key) {
      if (node.right === null)
        node.right = newNode;
      else 
        this._insertNode(node.right, newNode);
    }
    else {
      node.copies += newNode.copies;
    }
  }

The _insertNode method is a private method used for the recursive insertion of nodes. It compares the key of the new node with the key of the current node to determine whether to move to the left or right subtree. If a node with the same key already exists, it increments the number of copies.

  search(key) {
    return this._searchNode(this.root, key);
  }

The search method searches for a book in the library. It calls the private _searchNode method, which performs a recursive search through the tree.

  _searchNode(node, key) {
    if (node === null) 
      return false;

    if (key < node.key) 
      return this._searchNode(node.left, key);
    else if (key > node.key) 
      return this._searchNode(node.right, key);
    else 
      return true;
  }

The _searchNode method recursively searches for a node with the given key. If the key is less than the current node's key, it searches the left subtree; if greater, it searches the right subtree. If the key is equal, it means the book is found.

lendBook(bookName, numCopies = 1) {
  const foundNode = this._findNode(this.root, bookName);
  if (foundNode && foundNode.copies >= numCopies) {
    foundNode.copies -= numCopies;
    console.log(`Successfully lent ${numCopies} copies of ${bookName}.`);
  } else if (foundNode && foundNode.copies < numCopies) {
    console.log(`Sorry, only ${foundNode.copies} copies of ${bookName} are available.`);
  } else {
    console.log(`${bookName} not found in the library.`);
  }
}

The lendBook method allows lending a specified number of copies of a book. It uses the private _findNode method to locate the node corresponding to the given book name. If the book is found and has enough copies, it decreases the number of copies and logs a success message. If there aren't enough copies, it logs a message indicating the shortage. If the book is not found, it indicates that the book is not in the library.

returnBook(bookName, numCopies = 1) {
  const foundNode = this._findNode(this.root, bookName);
  if (foundNode) {
    foundNode.copies += numCopies;
    console.log(`Successfully returned ${numCopies} copies of ${bookName}.`);
  } else {
    console.log(`${bookName} not found in the library.`);
  }
}

The returnBook method allows returning a specified number of copies of a book. It uses the private _findNode method to locate the node corresponding to the given book name. If the book is found, it increases the number of copies and logs a success message. If the book is not found, it indicates that the book is not in the library.

checkBookStatus(bookName) {
  const foundNode = this._findNode(this.root, bookName);
  if (foundNode) {
    console.log(`${bookName} - Available Copies: ${foundNode.copies}`);
  } else {
    console.log(`${bookName} not found in the library.`);
  }
}

The checkBookStatus method checks and logs the available copies of a given book. It uses the private _findNode method to locate the node corresponding to the given book name. If the book is found, it logs the available copies. If the book is not found, it indicates that the book is not in the library.

_findNode(node, key) {
  if (node === null) return null;
  if (key < node.key) return this._findNode(node.left, key);
  else if (key > node.key) return this._findNode(node.right, key);
  else return node;
}

The _findNode method is a private method used for finding a node with a given key in a recursive manner. It starts at the root and navigates through the tree based on the comparison of keys until it finds the node with the matching key or reaches a leaf node.

printLibraryStatus() {
  this._inOrderTraversal(this.root);
}

The printLibraryStatus method initiates the process of printing the status of the library. It calls the private _inOrderTraversal method to perform an in-order traversal of the tree, printing the details of each book in sorted order.

_inOrderTraversal(node) {
  if (node !== null) {
    this._inOrderTraversal(node.left);
    console.log(`Book: ${node.key} - Available Copies: ${node.copies}`);
    this._inOrderTraversal(node.right);
  }
}

The _inOrderTraversal method is a private method used for traversing the tree in an in-order manner. It recursively visits the left subtree, prints the details of the current node, and then recursively visits the right subtree. This results in printing the books in sorted order based on their keys.

These methods collectively provide the functionality for managing a library, including adding books, lending copies, returning copies, checking book status, and printing the overall library status.

Implementing Library Management System

After defining our binary search tree, we import it into our main file to use for the library management system.

"use strict";

const readlineSync = require('readline-sync');
const BinarySearchTree = require('./binarySearchTree.js');

const library = new BinarySearchTree();

function displayMenu() {
    console.log('1. Add Book');
    console.log('2. Search Book');
    console.log('3. Lend Book');
    console.log('4. Return Book');
    console.log('5. Check Book Status');
    console.log('6. Print Library Status');
    console.log('7. Exit');
}

while (true) {
    displayMenu();
    const choice = readlineSync.questionInt('Enter your choice: ');

    switch (choice) {
        case 1:
            const bookName = readlineSync.question('Enter book name: ');
            const numCopies = readlineSync.questionInt('Enter number of copies: ');
            library.insert(bookName, numCopies);
            console.log('Book added successfully!');
            break;

        case 2:
            const searchBook = readlineSync.question('Enter book name to search: ');
            const isFound = library.search(searchBook);
            if (isFound)
                console.log('Book found in the library');
            else
                console.log('Book not found in the library');
            break;

        case 3:
            const lendBookName = readlineSync.question('Enter book name to lend: ');
            const lendCopies = readlineSync.questionInt('Enter number of copies to lend: ');
            library.lendBook(lendBookName, lendCopies);
            break;

        case 4:
            const returnBookName = readlineSync.question('Enter book name to return: ');
            const returnCopies = readlineSync.questionInt('Enter number of copies to return: ');
            library.returnBook(returnBookName, returnCopies);
            break;

        case 5:
            const statusBook = readlineSync.question('Enter book name to check status: ');
            library.checkBookStatus(statusBook);
            break;

        case 6:
            console.log('Library Status:');
            library.printLibraryStatus();
            break;

        case 7:
            console.log('Exiting the application.');
            process.exit(0);
            break;

        default:
            console.log('Invalid choice. Please try again.');
    }
}

In this implementation, we create a simple CLI application for a Library Management System. The program utilizes a Binary Search Tree (BST) to manage the library's books. The user is presented with a menu where they can perform various operations such as adding books, searching for books, lending copies, returning copies, checking book status, printing the library status, and exiting the application.

The Binary Search Tree functionalities, as explained earlier, are seamlessly integrated into the main loop, allowing users to interact with the library through a user-friendly command line interface. The program ensures a structured and efficient approach to managing library operations with the help of a Binary Search Tree data structure.

See the full code: Github Repository

Conclusion

In conclusion, we have successfully developed a Library Management System using the power of Binary Search Trees. This system provides a robust solution for efficiently managing books in a library, with intuitive functionalities accessible through a user-friendly CLI.

With this article at OpenGenus.org, you must have the complete idea of designing and implementing Library Management System using Binary Search Tree (BST).