DEV Community: Priyadharshini Selvaraj

Mastering JavaScript Internals#2 The Parser & AST

Priyadharshini Selvaraj — Wed, 01 Apr 2026 10:52:02 +0000

The Parser: How JavaScript Actually Reads Your Code

You type some JavaScript. You hit run. And it works.

But between those two moments, something fascinating happens — your code gets read, understood, and transformed before a single instruction executes. That process is called parsing, and it's the very first thing the engine does.

Let's walk through it, step by step.

🗺️ The Big Picture: 3 Steps Before Execution

When the JavaScript engine receives your code, it does three things in order:

Your Code (text)
      ↓
1. Tokenizing  →  breaks code into small labelled pieces
      ↓
2. Parsing     →  builds a tree structure from those pieces
      ↓
3. Compiling   →  turns the tree into something it can run

Today we're focusing on steps 1 and 2. Step 3 (compilation & JIT) is Post 3.

Step 1: Tokenizing — Breaking Code into Pieces

The very first thing the engine does is read your source code character by character and group them into meaningful chunks called tokens.

Here's a simple example:

const age = 25;

The engine sees this as:

Token	Type
`const`	Keyword
`age`	Identifier
`=`	Operator
`25`	Number literal
`;`	Punctuation

That's it. The tokenizer doesn't care about meaning yet — it just labels every piece of your code.

💡 Confused? Think of tokenizing like a spell-checker reading a sentence. It doesn't understand the sentence yet — it just identifies each word and punctuation mark one at a time. Only after that does it start to make sense of the grammar.

Step 2: Parsing — Building the Tree (AST)

Once the engine has a list of tokens, it needs to understand the structure of your code — how those tokens relate to each other.

It does this by building an Abstract Syntax Tree, or AST.

💡 Confused by "Abstract Syntax Tree"? Don't let the name intimidate you. It's just a tree diagram that represents your code's structure. "Abstract" means it strips away things like whitespace and semicolons — only the meaningful structure remains. "Syntax" means it's based on the grammar rules of JavaScript. "Tree" because it branches out like a family tree.

Here's what the AST looks like for our example:

const age = 25;

VariableDeclaration (const)
└── VariableDeclarator
    ├── Identifier: age
    └── NumericLiteral: 25

Even for one line of code, there's a whole tree. Let's try something slightly more complex:

function greet(name) {
  return "Hello, " + name;
}

FunctionDeclaration
├── Identifier: greet
├── Param: Identifier (name)
└── BlockStatement
    └── ReturnStatement
        └── BinaryExpression (+)
            ├── StringLiteral: "Hello, "
            └── Identifier: name

Notice how the tree captures the nesting of your code — the return is inside the function, the + operation is inside the return, and so on.

💡 Why does this matter to me as a developer? Every modern tool you use — Babel, ESLint, Prettier, TypeScript — reads and manipulates this tree. When ESLint catches a bug or Prettier reformats your code, it's working with the AST. Understanding this helps you understand your tools.

🚀 Lazy vs. Eager Parsing: A Smart Shortcut

Here's something interesting: the engine doesn't fully parse all your code upfront.

It uses two modes:

Eager parsing — fully parse this right now, we'll need it immediately.
Lazy parsing — just skim this for now, fully parse it later if it's actually called.

// This gets eagerly parsed — it runs immediately
console.log("app started");

// This gets lazily parsed — it's a function, only parsed fully when called
function heavySetup() {
  // ... lots of code
}

💡 Confused? Lazy parsing is like skimming a book's table of contents before reading each chapter in full. The engine skims functions it hasn't needed yet, saving time on startup. This is why large JavaScript apps can start up faster than you'd expect — the engine defers work it doesn't need right away.

This is also why wrapping everything in functions can sometimes hurt startup time — if the engine has to parse more eagerly than expected.

❌ When Parsing Goes Wrong: Syntax Errors

If your code breaks a grammar rule, the parser throws a SyntaxError before anything runs.

const x = ; // SyntaxError: Unexpected token ';'

The parser expected a value after =, but got ; instead. It can't build a valid tree from this, so it stops immediately.

💡 Confused? This is why syntax errors feel different from runtime errors. A runtime error happens during execution (e.g. TypeError: cannot read property of undefined). A syntax error happens before execution — the engine couldn't even read your code properly. Nothing runs until the syntax is valid.

🛠️ You Can See the AST Yourself

Want to explore this hands-on? Visit astexplorer.net and paste any JavaScript code. You'll see the full AST in real time — every node, every branch.

Try pasting:

const double = (n) => n * 2;

You'll immediately see how even a simple arrow function becomes a rich tree structure. It's the best way to make this click.

📝 Quick Recap

Here's what happens before your code runs:

Tokenizing — the engine reads your source text and splits it into labelled tokens.
Parsing — tokens are assembled into an AST that captures the structure of your code.
The engine uses lazy parsing to skip functions it doesn't need yet — saving startup time.
If your code has a grammar mistake, a SyntaxError is thrown and nothing runs.

➡️ Up Next

Post 3 — JIT Compilation: How JavaScript Goes From Slow to Fast

Now that the engine has an AST, it needs to turn it into something the computer can actually execute. We'll cover bytecode, the Ignition interpreter, and how Turbofan turns your hot functions into blazing-fast machine code.

Tried astexplorer.net? Drop a comment with something surprising you found in your own code's AST!

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on JavaScript internals, data structures, and algorithms!

Mastering JavaScript Internals #1 - Introduction

Priyadharshini Selvaraj — Wed, 01 Apr 2026 10:45:59 +0000

Why "I Know JavaScript" Isn't Enough Anymore

You write JavaScript every day. You ship features, fix bugs, and get things done.

But have you ever wondered why your code actually works? Not just what it does — but what happens underneath, the moment you hit run?

That's what this series is about. No fluff. No theory for theory's sake. Just a clear, honest look at what's really going on inside JavaScript — explained simply, one layer at a time.

🤔 The Gap Most Developers Don't Know Exists

Here's the thing: JavaScript doesn't just "run." It goes through a whole journey before a single line of your code executes.

Think of it like this:

You write a recipe (your JS code) → a chef reads it (the engine) → the chef decides the most efficient way to cook it (optimization) → the food gets made (execution).

Most developers only think about the recipe. This series teaches you to understand the chef.

🧱 The 6 Things We'll Cover

Here's a quick plain-English overview of the six topics in this series:

1. 🔍 How the Engine Reads Your Code

Before your code runs, JavaScript reads it top to bottom, breaks it into small pieces (called tokens), and builds a map of your program called an AST (Abstract Syntax Tree).

💡 Confused? Think of the AST like a family tree of your code. The engine needs to understand the structure of what you wrote before it can run it. You don't need to memorise this — just know it happens behind the scenes every single time.

2. ⚡ Why JavaScript Gets Faster the More It Runs

JavaScript starts slow, then speeds up. That's because of something called JIT (Just-In-Time) compilation.

The simple version: the engine watches your code as it runs. If it sees you calling the same function over and over, it compiles that function into super-fast machine code automatically.

💡 Confused? JIT is like a chef who notices you always order the same dish and starts prepping it before you even ask. It's an optimisation that happens automatically — but it can also backfire if your code is inconsistent (e.g. passing a number to a function that usually gets a string). We'll cover exactly how to avoid this.

3. 🧠 Where Your Data Actually Lives

Every variable, object, and function you create takes up memory somewhere. But where?

Simple values like 1, true, "hello" live on the stack — fast and short-lived.
Objects and arrays live on the heap — a larger, slower storage area.

JavaScript also has a garbage collector that automatically cleans up memory you're no longer using.

💡 Confused? The stack and heap are just two different compartments in your computer's memory. You don't manage them manually in JS — but understanding them helps you avoid accidentally holding onto memory you don't need. That's called a memory leak, and it can silently slow down or crash your app over time.

4. 🔗 How Scope, `this`, and Prototypes Actually Work

These three are responsible for more confusion than almost anything else in JavaScript.

Scope = what variables your code can "see" at any given point.
this = which object a function "belongs to" when it runs.
Prototypes = how objects inherit properties from other objects.

💡 Confused by this? You're not alone — it's one of the most commonly misunderstood parts of JS. If you've ever seen this is undefined inside a callback, that's a scope/context bug. We'll build a clear mental model so this never trips you up again.

5. 🔄 The Event Loop (the Real Version)

You've probably heard: "JavaScript is single-threaded and uses an event loop." But what does that actually mean day-to-day?

Short version: JavaScript can only do one thing at a time. But it appears to do many things at once because it queues tasks up and processes them in a very specific order.

💡 Confused? Picture a single cashier at a supermarket. They can only serve one customer at a time — but while the customer is tapping their card, the cashier is already scanning the next item. The event loop is that cashier's system for deciding what to do next. Understanding this order is why some async/await bugs are so hard to track down — and why we'll go deep on it.

6. 📦 Modules, Bundlers & Performance

How does import actually work under the hood? What does Webpack or Vite really do to your files? What even is tree-shaking?

This section connects everything back to the tools you use every day.

💡 Confused by bundlers? A bundler takes all your separate JS files and stitches them into one optimised file for the browser. Tree-shaking means it automatically removes code you imported but never used — like trimming dead branches off a tree so the bundle stays lean and fast.

📋 What to Expect from Each Post

Every post in this series will:

Explain one concept deeply — no skimming, no hand-waving
Use real analogies so the idea clicks before the code does
Show code examples that tie theory to practice
Flag confusing bits with a 💡 callout — just like above

✅ What You'll Be Able to Do After This Series

Understand why your code is slow — and actually fix it
Debug async and Promise bugs without guessing
Avoid sneaky memory mistakes
Read a performance profiler and know what you're looking at
Make smarter decisions about tools, patterns, and architecture

➡️ Up Next

Post 2 — The Parser: How JavaScript Reads Your Code

We'll follow a simple function from the moment you type it to the moment the engine is ready to run it — step by step, no jargon left unexplained.

Drop a comment if there's something specific you've always found confusing about JS internals — it might shape the next post.

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on JavaScript internals, data structures, and algorithms!

Data Structures Series #4: Graphs - Implementation & Use Cases

Priyadharshini Selvaraj — Wed, 01 Apr 2026 10:24:05 +0000

Introduction

Welcome back to the Data Structures series! So far we've covered Stacks, Queues, and Binary Trees. Today we're exploring one of the most versatile and powerful data structures in computer science: Graphs. From social networks to GPS navigation, graphs model relationships between things in ways other structures simply can't. Let's dig in.

What is a Graph?

A Graph is a non-linear data structure made up of vertices (also called nodes) and edges (connections between nodes). Unlike trees, graphs have no strict parent-child hierarchy — any node can connect to any other node.

Key Terminology

Vertex (Node): A single entity in the graph (e.g., a user, a city).
Edge: A connection between two vertices.
Directed Graph: Edges have a direction (A → B, but not B → A). Think Twitter followers.
Undirected Graph: Edges go both ways (A — B). Think Facebook friends.
Weighted Graph: Edges carry a cost or distance value. Think Google Maps routes.
Adjacency: Two vertices are adjacent if they share an edge.

Undirected Graph Example:

    A --- B
    |     |
    C --- D

Implementing a Graph in JavaScript

The most common way to represent a graph is with an Adjacency List — an object where each key is a vertex and its value is an array of connected vertices. It's memory-efficient and easy to work with.

Basic Graph Class

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  // Add a vertex
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  // Add an undirected edge
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  // Remove an edge
  removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
    this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
  }

  // Remove a vertex and all its edges
  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacent = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacent);
    }
    delete this.adjacencyList[vertex];
  }
}

// Usage
const graph = new Graph();
graph.addVertex("Alice");
graph.addVertex("Bob");
graph.addVertex("Carol");
graph.addEdge("Alice", "Bob");
graph.addEdge("Bob", "Carol");
graph.addEdge("Alice", "Carol");

console.log(graph.adjacencyList);
// { Alice: ["Bob", "Carol"], Bob: ["Alice", "Carol"], Carol: ["Bob", "Alice"] }

Graph Traversals

Traversal means visiting every vertex in the graph. There are two fundamental approaches.

1. Depth-First Search (DFS)

DFS explores as far as possible along a branch before backtracking. It uses a stack (or recursion) to track the path.

// Recursive DFS
dfs(start) {
  const result = [];
  const visited = {};

  const explore = (vertex) => {
    if (!vertex) return;
    visited[vertex] = true;
    result.push(vertex);

    this.adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) explore(neighbor);
    });
  };

  explore(start);
  return result;
}

Use DFS when: you want to detect cycles, solve puzzles (like mazes), or find a path between two nodes.

2. Breadth-First Search (BFS)

BFS explores all neighbours at the current level before moving deeper. It uses a queue and is ideal for finding the shortest path.

bfs(start) {
  const queue = [start];
  const result = [];
  const visited = { [start]: true };

  while (queue.length) {
    const vertex = queue.shift();
    result.push(vertex);

    this.adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }

  return result;
}

Use BFS when: you need the shortest path, level-by-level exploration, or finding nodes within a certain distance.

DFS vs BFS — Quick Comparison

Feature	DFS	BFS
Data Structure	Stack / Recursion	Queue
Memory Usage	Lower (for sparse graphs)	Higher (stores all levels)
Shortest Path	❌ Not guaranteed	✅ Yes (unweighted graphs)
Best For	Cycles, paths, topological sort	Shortest path, level traversal

Real-World Use Cases

Social Networks: Finding friends-of-friends (BFS), detecting communities.
GPS & Navigation: Shortest route between cities using weighted graphs (Dijkstra's algorithm builds on BFS).
Web Crawlers: Crawling links from page to page using DFS.
Recommendation Engines: "People you may know" or "Products you might like."
Dependency Resolution: Package managers (like npm) use directed graphs to resolve module dependencies.

Time and Space Complexity

Let V = number of vertices, E = number of edges.

Operation	Adjacency List	Adjacency Matrix
Add Vertex	O(1)	O(V²)
Add Edge	O(1)	O(1)
Remove Edge	O(E)	O(1)
DFS / BFS	O(V + E)	O(V²)
Space	O(V + E)	O(V²)

Adjacency List is preferred for sparse graphs (fewer edges) — which is the common real-world case. Adjacency Matrix can be useful when you need fast edge lookups in dense graphs.

Conclusion

Graphs are one of the richest and most applicable data structures you'll encounter. Once you understand vertices, edges, and the two core traversal strategies — DFS and BFS — you unlock the ability to model and solve a huge class of real-world problems.

Key takeaways:

Use an adjacency list for most graph implementations.
Use BFS for shortest paths and level-order traversal.
Use DFS for cycle detection, backtracking, and deep exploration.
Graphs power social networks, navigation, search engines, and much more.

Stay tuned for the next post in the series!

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!

RAG and LangChain Basics

Priyadharshini Selvaraj — Sat, 07 Jun 2025 03:26:42 +0000

Introduction

Large Language Models (LLMs) like GPT-4 and Claude are incredibly powerful, but they have a significant limitation: they can only work with information they were trained on. What if you want your AI application to access your company's internal documents, real-time data, or domain-specific knowledge? This is where Retrieval-Augmented Generation (RAG) comes in, and LangChain makes implementing RAG systems remarkably straightforward.

What is RAG?

RAG is an architectural pattern that combines the generative capabilities of LLMs with external knowledge retrieval. Instead of relying solely on the model's pre-trained knowledge, RAG systems first retrieve relevant information from external sources, then use that context to generate more accurate and up-to-date responses.

Traditional LLM vs RAG Architecture

Traditional LLM:
User Query → LLM → Response (limited to training data)

RAG System:
User Query → Retrieve Relevant Docs → LLM + Context → Enhanced Response

Key Benefits of RAG:

Access to current, domain-specific information
Reduced hallucinations through grounded responses
Cost-effective alternative to fine-tuning
Easy to update knowledge base without retraining

RAG System Architecture

The RAG pipeline consists of two main phases:

1. Indexing Phase (Data Preparation)

Document Loading: Ingest documents from various sources (PDFs, web pages, databases)
Text Splitting: Break documents into manageable chunks
Embedding: Convert text chunks into vector representations
Storage: Store embeddings in a vector database

2. Retrieval Phase (Query Processing)

Query Embedding: Convert user query to vector format
Similarity Search: Find most relevant document chunks
Context Assembly: Combine retrieved chunks with the original query
Generation: LLM generates response using augmented context

Enter LangChain

LangChain is a framework that simplifies building applications with LLMs. It provides abstractions and tools that make implementing RAG systems much easier than building from scratch.

Core LangChain Components for RAG

# Document Loading
from langchain.document_loaders import PyPDFLoader, WebBaseLoader

# Text Splitting
from langchain.text_splitter import RecursiveCharacterTextSplitter

# Embeddings
from langchain.embeddings import OpenAIEmbeddings

# Vector Stores
from langchain.vectorstores import Chroma, Pinecone

# LLMs
from langchain.llms import OpenAI
from langchain.chat_models import ChatOpenAI

# Chains
from langchain.chains import RetrievalQA

Building a RAG System with LangChain

Let's walk through creating a simple RAG system that can answer questions about your documentation:

Step 1: Document Ingestion and Processing

from langchain.document_loaders import DirectoryLoader
from langchain.text_splitter import RecursiveCharacterTextSplitter
from langchain.embeddings import OpenAIEmbeddings
from langchain.vectorstores import Chroma

# Load documents
loader = DirectoryLoader('./docs', glob="**/*.md")
documents = loader.load()

# Split into chunks
text_splitter = RecursiveCharacterTextSplitter(
    chunk_size=1000,
    chunk_overlap=200
)
splits = text_splitter.split_documents(documents)

# Create embeddings and vector store
embeddings = OpenAIEmbeddings()
vectorstore = Chroma.from_documents(
    documents=splits,
    embedding=embeddings
)

Step 2: Setting up the Retrieval Chain

from langchain.chains import RetrievalQA
from langchain.chat_models import ChatOpenAI

# Initialize LLM
llm = ChatOpenAI(model_name="gpt-3.5-turbo", temperature=0)

# Create retrieval chain
qa_chain = RetrievalQA.from_chain_type(
    llm=llm,
    chain_type="stuff",
    retriever=vectorstore.as_retriever(
        search_kwargs={"k": 3}  # Retrieve top 3 relevant chunks
    )
)

# Query the system
response = qa_chain.run("How do I implement authentication?")
print(response)

RAG Query Flow Visualization

┌─────────────────┐    ┌──────────────────┐    ┌─────────────────┐
│   User Query    │───▶│  Vector Search   │───▶│  Top K Chunks   │
│"How to deploy?" │    │   (Similarity)   │    │   Retrieved     │
└─────────────────┘    └──────────────────┘    └─────────────────┘
                                                        │
                                                        ▼
┌─────────────────┐    ┌──────────────────┐    ┌─────────────────┐
│Final Response   │◀───│      LLM         │◀───│  Query + Context│
│  (Grounded)     │    │   Generation     │    │   Combined      │
└─────────────────┘    └──────────────────┘    └─────────────────┘

Advanced RAG Patterns

1. Multi-Query Retrieval

Generate multiple variations of the user query to improve retrieval quality:

from langchain.retrievers import MultiQueryRetriever

retriever = MultiQueryRetriever.from_llm(
    retriever=vectorstore.as_retriever(),
    llm=llm
)

2. Contextual Compression

Filter retrieved documents to only include relevant portions:

from langchain.retrievers import ContextualCompressionRetriever
from langchain.retrievers.document_compressors import LLMChainExtractor

compressor = LLMChainExtractor.from_llm(llm)
compression_retriever = ContextualCompressionRetriever(
    base_compressor=compressor,
    base_retriever=vectorstore.as_retriever()
)

3. Self-Query Retrieval

Allow the system to construct filters based on query metadata:

from langchain.retrievers.self_query.base import SelfQueryRetriever

retriever = SelfQueryRetriever.from_llm(
    llm=llm,
    vectorstore=vectorstore,
    document_contents="Technical documentation",
    metadata_field_info=metadata_field_info
)

Best Practices for Production RAG Systems

Data Quality and Chunking Strategy

Optimal Chunk Size: 500-1000 characters with 100-200 character overlap
Preserve Context: Avoid splitting mid-sentence or breaking logical units
Metadata Enrichment: Add source, timestamp, and category information

Retrieval Optimization

Hybrid Search: Combine semantic and keyword search
Reranking: Use cross-encoders to improve retrieval quality
Evaluation Metrics: Track retrieval precision, recall, and end-to-end accuracy

Performance Considerations

# Async processing for better performance
from langchain.chains import AsyncLLMChain

# Caching for repeated queries
from langchain.cache import InMemoryCache
import langchain
langchain.llm_cache = InMemoryCache()

# Streaming responses
def stream_response(query):
    for chunk in qa_chain.stream({"query": query}):
        yield chunk

Real-World Applications

RAG systems are being used across various domains:

Customer Support: AI chatbots with access to knowledge bases
Legal Research: Query legal documents and case law
Medical Assistance: Access medical literature and guidelines
Code Documentation: Developer tools with codebase awareness
Educational Content: Personalized learning with curriculum access

Conclusion

RAG represents a paradigm shift in how we build AI applications. By combining the power of LLMs with external knowledge retrieval, we can create systems that are both intelligent and grounded in factual information. LangChain makes this implementation accessible to developers, providing the tools and abstractions needed to build production-ready RAG systems.

The key to successful RAG implementation lies in understanding your data, optimizing your retrieval strategy, and continuously evaluating system performance. As the field evolves, we're seeing more sophisticated approaches like agentic RAG, multi-modal retrieval, and graph-based knowledge systems.

Start small with a simple RAG system using LangChain, then gradually incorporate advanced patterns as your needs grow. The future of AI applications is not just about better models, but about better ways to ground those models in real-world knowledge.

Ready to build your own RAG system? Check out the LangChain documentation and start experimenting with your own documents today!

Data Structures Series #3: Binary Trees - Implementation & Use Cases

Priyadharshini Selvaraj — Sat, 07 Jun 2025 03:01:16 +0000

Introduction

Welcome back to my tech blog series on data structures! Today, we're exploring Binary Trees, a fundamental hierarchical data structure that forms the backbone of many advanced algorithms and applications. We'll implement binary trees in JavaScript, dive into traversal methods, and discover how they power everything from file systems to search algorithms.

What is a Binary Tree?

A Binary Tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. Unlike linear data structures (arrays, linked lists, stacks, queues), binary trees organize data in a tree-like structure that allows for efficient searching, insertion, and deletion operations.

Key Terminology:

Node – An element containing data and references to child nodes
Root – The topmost node in the tree
Leaf – A node with no children
Parent – A node that has one or more child nodes
Subtree – A tree formed by a node and all its descendants
Height – The longest path from root to any leaf
Depth – The distance from root to a specific node

Basic Binary Tree Implementation

Let's start with a simple binary tree implementation:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  // Insert node (basic insertion - not BST rules)
  insert(value) {
    const newNode = new TreeNode(value);

    if (!this.root) {
      this.root = newNode;
      return;
    }

    const queue = [this.root];

    while (queue.length > 0) {
      const current = queue.shift();

      if (!current.left) {
        current.left = newNode;
        return;
      } else if (!current.right) {
        current.right = newNode;
        return;
      }

      queue.push(current.left, current.right);
    }
  }

  // Search for a value
  search(value) {
    return this._searchRecursive(this.root, value);
  }

  _searchRecursive(node, value) {
    if (!node) return false;
    if (node.value === value) return true;

    return this._searchRecursive(node.left, value) || 
           this._searchRecursive(node.right, value);
  }

  // Get tree height
  getHeight() {
    return this._getHeightRecursive(this.root);
  }

  _getHeightRecursive(node) {
    if (!node) return -1;

    const leftHeight = this._getHeightRecursive(node.left);
    const rightHeight = this._getHeightRecursive(node.right);

    return Math.max(leftHeight, rightHeight) + 1;
  }

  // Count total nodes
  getSize() {
    return this._getSizeRecursive(this.root);
  }

  _getSizeRecursive(node) {
    if (!node) return 0;
    return 1 + this._getSizeRecursive(node.left) + this._getSizeRecursive(node.right);
  }
}

// Usage example
const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);

console.log(tree.search(7)); // true
console.log(tree.getHeight()); // 2
console.log(tree.getSize()); // 5

Binary Tree Traversal Methods

Tree traversal is the process of visiting each node exactly once. There are several ways to traverse a binary tree:

1. Depth-First Search (DFS) Traversals

class BinaryTree {
  // ... previous code ...

  // In-order traversal: Left → Root → Right
  inOrderTraversal() {
    const result = [];
    this._inOrderRecursive(this.root, result);
    return result;
  }

  _inOrderRecursive(node, result) {
    if (node) {
      this._inOrderRecursive(node.left, result);
      result.push(node.value);
      this._inOrderRecursive(node.right, result);
    }
  }

  // Pre-order traversal: Root → Left → Right
  preOrderTraversal() {
    const result = [];
    this._preOrderRecursive(this.root, result);
    return result;
  }

  _preOrderRecursive(node, result) {
    if (node) {
      result.push(node.value);
      this._preOrderRecursive(node.left, result);
      this._preOrderRecursive(node.right, result);
    }
  }

  // Post-order traversal: Left → Right → Root
  postOrderTraversal() {
    const result = [];
    this._postOrderRecursive(this.root, result);
    return result;
  }

  _postOrderRecursive(node, result) {
    if (node) {
      this._postOrderRecursive(node.left, result);
      this._postOrderRecursive(node.right, result);
      result.push(node.value);
    }
  }
}

2. Breadth-First Search (BFS) - Level Order Traversal

class BinaryTree {
  // ... previous code ...

  // Level-order traversal: Visit nodes level by level
  levelOrderTraversal() {
    if (!this.root) return [];

    const result = [];
    const queue = [this.root];

    while (queue.length > 0) {
      const current = queue.shift();
      result.push(current.value);

      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.right);
    }

    return result;
  }

  // Get nodes at each level separately
  getLevelOrder() {
    if (!this.root) return [];

    const levels = [];
    const queue = [this.root];

    while (queue.length > 0) {
      const levelSize = queue.length;
      const currentLevel = [];

      for (let i = 0; i < levelSize; i++) {
        const node = queue.shift();
        currentLevel.push(node.value);

        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
      }

      levels.push(currentLevel);
    }

    return levels;
  }
}

// Usage
const tree = new BinaryTree();
[10, 5, 15, 3, 7, 12, 20].forEach(val => tree.insert(val));

console.log('In-order:', tree.inOrderTraversal());     // [3, 5, 7, 10, 12, 15, 20]
console.log('Pre-order:', tree.preOrderTraversal());   // [10, 5, 3, 7, 15, 12, 20]
console.log('Post-order:', tree.postOrderTraversal()); // [3, 7, 5, 12, 20, 15, 10]
console.log('Level-order:', tree.levelOrderTraversal()); // [10, 5, 15, 3, 7, 12, 20]
console.log('By levels:', tree.getLevelOrder()); // [[10], [5, 15], [3, 7, 12, 20]]

Binary Search Tree (BST)

A Binary Search Tree is a special type of binary tree where:

Left subtree contains only nodes with values less than the parent
Right subtree contains only nodes with values greater than the parent
Both subtrees are also BSTs

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

  insert(value) {
    this.root = this._insertRecursive(this.root, value);
  }

  _insertRecursive(node, value) {
    if (!node) {
      return new TreeNode(value);
    }

    if (value < node.value) {
      node.left = this._insertRecursive(node.left, value);
    } else if (value > node.value) {
      node.right = this._insertRecursive(node.right, value);
    }
    // If value equals node.value, we don't insert duplicates

    return node;
  }

  search(value) {
    return this._searchRecursive(this.root, value);
  }

  _searchRecursive(node, value) {
    if (!node) return false;
    if (node.value === value) return true;

    if (value < node.value) {
      return this._searchRecursive(node.left, value);
    } else {
      return this._searchRecursive(node.right, value);
    }
  }

  findMin() {
    if (!this.root) return null;

    let current = this.root;
    while (current.left) {
      current = current.left;
    }
    return current.value;
  }

  findMax() {
    if (!this.root) return null;

    let current = this.root;
    while (current.right) {
      current = current.right;
    }
    return current.value;
  }

  delete(value) {
    this.root = this._deleteRecursive(this.root, value);
  }

  _deleteRecursive(node, value) {
    if (!node) return null;

    if (value < node.value) {
      node.left = this._deleteRecursive(node.left, value);
    } else if (value > node.value) {
      node.right = this._deleteRecursive(node.right, value);
    } else {
      // Node to delete found

      // Case 1: Node has no children (leaf)
      if (!node.left && !node.right) {
        return null;
      }

      // Case 2: Node has one child
      if (!node.left) return node.right;
      if (!node.right) return node.left;

      // Case 3: Node has two children
      // Find the inorder successor (smallest in right subtree)
      let successor = node.right;
      while (successor.left) {
        successor = successor.left;
      }

      // Replace node's value with successor's value
      node.value = successor.value;

      // Delete the successor
      node.right = this._deleteRecursive(node.right, successor.value);
    }

    return node;
  }

  // In-order traversal gives sorted order for BST
  getSortedValues() {
    const result = [];
    this._inOrderTraversal(this.root, result);
    return result;
  }

  _inOrderTraversal(node, result) {
    if (node) {
      this._inOrderTraversal(node.left, result);
      result.push(node.value);
      this._inOrderTraversal(node.right, result);
    }
  }
}

// Usage
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));

console.log('Sorted values:', bst.getSortedValues()); // [20, 30, 40, 50, 60, 70, 80]
console.log('Min value:', bst.findMin()); // 20
console.log('Max value:', bst.findMax()); // 80
console.log('Search 40:', bst.search(40)); // true

bst.delete(30);
console.log('After deleting 30:', bst.getSortedValues()); // [20, 40, 50, 60, 70, 80]

Real-World Use Cases of Binary Trees

1. File System Directory Structure

File systems use tree structures to organize directories and files:

class FileSystemNode {
  constructor(name, isDirectory = false) {
    this.name = name;
    this.isDirectory = isDirectory;
    this.children = [];
    this.parent = null;
    this.size = isDirectory ? 0 : Math.floor(Math.random() * 1000); // Random file size
  }
}

class FileSystem {
  constructor() {
    this.root = new FileSystemNode('/', true);
  }

  createDirectory(path) {
    const parts = path.split('/').filter(part => part);
    let current = this.root;

    for (const part of parts) {
      let found = current.children.find(child => child.name === part);
      if (!found) {
        found = new FileSystemNode(part, true);
        found.parent = current;
        current.children.push(found);
      }
      current = found;
    }
  }

  createFile(path, filename) {
    this.createDirectory(path);
    const directory = this.findNode(path);

    if (directory && !directory.children.find(child => child.name === filename)) {
      const file = new FileSystemNode(filename, false);
      file.parent = directory;
      directory.children.push(file);
    }
  }

  findNode(path) {
    if (path === '/') return this.root;

    const parts = path.split('/').filter(part => part);
    let current = this.root;

    for (const part of parts) {
      const found = current.children.find(child => child.name === part);
      if (!found) return null;
      current = found;
    }

    return current;
  }

  listDirectory(path) {
    const node = this.findNode(path);
    if (!node || !node.isDirectory) return [];

    return node.children.map(child => ({
      name: child.name,
      type: child.isDirectory ? 'directory' : 'file',
      size: child.isDirectory ? this.getDirectorySize(child) : child.size
    }));
  }

  getDirectorySize(node) {
    if (!node.isDirectory) return node.size;

    return node.children.reduce((total, child) => {
      return total + (child.isDirectory ? this.getDirectorySize(child) : child.size);
    }, 0);
  }

  printTree(node = this.root, indent = '') {
    console.log(indent + (node.isDirectory ? '📁 ' : '📄 ') + node.name);

    if (node.isDirectory) {
      node.children.forEach(child => {
        this.printTree(child, indent + '  ');
      });
    }
  }
}

// Usage
const fs = new FileSystem();
fs.createDirectory('/home/user/documents');
fs.createDirectory('/home/user/pictures');
fs.createFile('/home/user/documents', 'resume.pdf');
fs.createFile('/home/user/documents', 'notes.txt');
fs.createFile('/home/user/pictures', 'vacation.jpg');

fs.printTree();
console.log('Documents:', fs.listDirectory('/home/user/documents'));

2. Expression Tree for Mathematical Expressions

Binary trees can represent mathematical expressions for parsing and evaluation:

class ExpressionTree {
  constructor() {
    this.operators = new Set(['+', '-', '*', '/', '^']);
  }

  buildFromPostfix(postfix) {
    const stack = [];

    for (const token of postfix) {
      if (this.operators.has(token)) {
        const right = stack.pop();
        const left = stack.pop();
        const node = new TreeNode(token);
        node.left = left;
        node.right = right;
        stack.push(node);
      } else {
        stack.push(new TreeNode(parseFloat(token)));
      }
    }

    return stack[0];
  }

  evaluate(node) {
    if (!node) return 0;

    // If it's a number (leaf node)
    if (typeof node.value === 'number') {
      return node.value;
    }

    // If it's an operator
    const leftValue = this.evaluate(node.left);
    const rightValue = this.evaluate(node.right);

    switch (node.value) {
      case '+': return leftValue + rightValue;
      case '-': return leftValue - rightValue;
      case '*': return leftValue * rightValue;
      case '/': return leftValue / rightValue;
      case '^': return Math.pow(leftValue, rightValue);
      default: return 0;
    }
  }

  toInfix(node) {
    if (!node) return '';

    // If it's a number (leaf node)
    if (typeof node.value === 'number') {
      return node.value.toString();
    }

    // If it's an operator
    const left = this.toInfix(node.left);
    const right = this.toInfix(node.right);

    return `(${left} ${node.value} ${right})`;
  }
}

// Usage
const expressionTree = new ExpressionTree();

// Postfix: 3 4 + 2 * 7 /
// Infix: ((3 + 4) * 2) / 7
const postfix = ['3', '4', '+', '2', '*', '7', '/'];
const root = expressionTree.buildFromPostfix(postfix);

console.log('Infix:', expressionTree.toInfix(root)); // ((3 + 4) * 2) / 7
console.log('Result:', expressionTree.evaluate(root)); // 2

3. Decision Tree for AI/ML Applications

Binary trees are used in machine learning for decision-making processes:

class DecisionTreeNode {
  constructor(feature = null, threshold = null, value = null) {
    this.feature = feature;      // Feature to split on
    this.threshold = threshold;  // Threshold value
    this.value = value;         // Classification result (for leaf nodes)
    this.left = null;           // Left child (feature <= threshold)
    this.right = null;          // Right child (feature > threshold)
  }

  isLeaf() {
    return this.value !== null;
  }
}

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

  // Build a simple decision tree for loan approval
  buildLoanApprovalTree() {
    // Root: Check credit score
    this.root = new DecisionTreeNode('creditScore', 650);

    // Left branch: Credit score <= 650
    this.root.left = new DecisionTreeNode('income', 50000);
    this.root.left.left = new DecisionTreeNode(null, null, 'REJECTED'); // Low credit, low income
    this.root.left.right = new DecisionTreeNode('employmentYears', 2);
    this.root.left.right.left = new DecisionTreeNode(null, null, 'REJECTED'); // Low credit, good income, short employment
    this.root.left.right.right = new DecisionTreeNode(null, null, 'APPROVED'); // Low credit, good income, long employment

    // Right branch: Credit score > 650
    this.root.right = new DecisionTreeNode('debtToIncome', 0.4);
    this.root.right.left = new DecisionTreeNode(null, null, 'APPROVED'); // Good credit, low debt ratio
    this.root.right.right = new DecisionTreeNode('income', 80000);
    this.root.right.right.left = new DecisionTreeNode(null, null, 'REJECTED'); // Good credit, high debt, low income
    this.root.right.right.right = new DecisionTreeNode(null, null, 'APPROVED'); // Good credit, high debt, high income
  }

  predict(applicant) {
    let current = this.root;

    while (!current.isLeaf()) {
      const featureValue = applicant[current.feature];

      if (featureValue <= current.threshold) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    return current.value;
  }

  printDecisionPath(applicant, node = this.root, path = []) {
    if (node.isLeaf()) {
      console.log('Decision path:', path.join(' → '));
      console.log('Final decision:', node.value);
      return;
    }

    const featureValue = applicant[node.feature];
    const condition = `${node.feature}: ${featureValue} ${featureValue <= node.threshold ? '≤' : '>'} ${node.threshold}`;

    if (featureValue <= node.threshold) {
      path.push(condition + ' (LEFT)');
      this.printDecisionPath(applicant, node.left, path);
    } else {
      path.push(condition + ' (RIGHT)');
      this.printDecisionPath(applicant, node.right, path);
    }
  }
}

// Usage
const decisionTree = new DecisionTree();
decisionTree.buildLoanApprovalTree();

const applicants = [
  {
    name: 'John',
    creditScore: 720,
    income: 65000,
    employmentYears: 3,
    debtToIncome: 0.3
  },
  {
    name: 'Jane',
    creditScore: 580,
    income: 45000,
    employmentYears: 1,
    debtToIncome: 0.5
  },
  {
    name: 'Bob',
    creditScore: 680,
    income: 95000,
    employmentYears: 5,
    debtToIncome: 0.6
  }
];

applicants.forEach(applicant => {
  console.log(`\n--- ${applicant.name} ---`);
  const decision = decisionTree.predict(applicant);
  console.log(`Decision: ${decision}`);
  decisionTree.printDecisionPath(applicant);
});

4. Auto-Complete/Search Suggestions (Trie Tree)

While not exactly a binary tree, Trie is another important tree structure used for string searching and auto-complete:

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
    this.frequency = 0; // For ranking suggestions
  }
}

class AutoComplete {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word, frequency = 1) {
    let current = this.root;

    for (const char of word.toLowerCase()) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }

    current.isEndOfWord = true;
    current.frequency = frequency;
  }

  getSuggestions(prefix, maxSuggestions = 5) {
    const node = this.findNode(prefix.toLowerCase());
    if (!node) return [];

    const suggestions = [];
    this.collectWords(node, prefix.toLowerCase(), suggestions);

    // Sort by frequency (descending) and return top suggestions
    return suggestions
      .sort((a, b) => b.frequency - a.frequency)
      .slice(0, maxSuggestions)
      .map(item => item.word);
  }

  findNode(prefix) {
    let current = this.root;

    for (const char of prefix) {
      if (!current.children.has(char)) {
        return null;
      }
      current = current.children.get(char);
    }

    return current;
  }

  collectWords(node, currentWord, suggestions) {
    if (node.isEndOfWord) {
      suggestions.push({
        word: currentWord,
        frequency: node.frequency
      });
    }

    for (const [char, childNode] of node.children) {
      this.collectWords(childNode, currentWord + char, suggestions);
    }
  }

  // Check if a word exists
  search(word) {
    const node = this.findNode(word.toLowerCase());
    return node !== null && node.isEndOfWord;
  }
}

// Usage
const autoComplete = new AutoComplete();

// Insert words with frequencies (simulating search popularity)
const words = [
  ['javascript', 1000],
  ['java', 800],
  ['python', 950],
  ['programming', 600],
  ['program', 400],
  ['project', 300],
  ['practice', 200],
  ['professional', 150]
];

words.forEach(([word, freq]) => autoComplete.insert(word, freq));

console.log('Suggestions for "ja":', autoComplete.getSuggestions('ja'));
// ['javascript', 'java']

console.log('Suggestions for "pro":', autoComplete.getSuggestions('pro'));
// ['programming', 'program', 'project', 'practice', 'professional']

console.log('Search "python":', autoComplete.search('python')); // true
console.log('Search "pythons":', autoComplete.search('pythons')); // false

5. Heap Implementation using Binary Tree

Heaps are complete binary trees used in priority queues and sorting algorithms:

class MinHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  hasParent(index) {
    return this.getParentIndex(index) >= 0;
  }

  hasLeftChild(index) {
    return this.getLeftChildIndex(index) < this.heap.length;
  }

  hasRightChild(index) {
    return this.getRightChildIndex(index) < this.heap.length;
  }

  parent(index) {
    return this.heap[this.getParentIndex(index)];
  }

  leftChild(index) {
    return this.heap[this.getLeftChildIndex(index)];
  }

  rightChild(index) {
    return this.heap[this.getRightChildIndex(index)];
  }

  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;

    while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index);
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();

    return min;
  }

  heapifyDown() {
    let index = 0;

    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);

      if (this.hasRightChild(index) && 
          this.rightChild(index) < this.leftChild(index)) {
        smallerChildIndex = this.getRightChildIndex(index);
      }

      if (this.heap[index] < this.heap[smallerChildIndex]) {
        break;
      }

      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  }

  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

// Usage in a task scheduler with priorities
class TaskScheduler {
  constructor() {
    this.taskHeap = new MinHeap();
    this.taskId = 0;
  }

  addTask(description, priority) {
    const task = {
      id: ++this.taskId,
      description,
      priority,
      createdAt: new Date()
    };

    // Insert with priority as the comparison value
    this.taskHeap.insert({ priority, task });
    console.log(`Task added: ${description} (Priority: ${priority})`);
  }

  processNextTask() {
    const taskItem = this.taskHeap.extractMin();

    if (!taskItem) {
      console.log('No tasks to process');
      return null;
    }

    console.log(`Processing: ${taskItem.task.description} (Priority: ${taskItem.priority})`);
    return taskItem.task;
  }

  getPendingTasks() {
    return this.taskHeap.size();
  }

  peekNextTask() {
    const taskItem = this.taskHeap.peek();
    return taskItem ? taskItem.task : null;
  }
}

// Usage
const scheduler = new TaskScheduler();

scheduler.addTask('Fix critical bug', 1);
scheduler.addTask('Update documentation', 5);
scheduler.addTask('Code review', 3);
scheduler.addTask('Security patch', 1);
scheduler.addTask('Feature development', 4);

console.log('\nProcessing tasks in priority order:');
while (scheduler.getPendingTasks() > 0) {
  scheduler.processNextTask();
}

Time and Space Complexity

Operation	Binary Tree	Binary Search Tree (Balanced)	Binary Search Tree (Unbalanced)
Search	O(n)	O(log n)	O(n)
Insert	O(n)	O(log n)	O(n)
Delete	O(n)	O(log n)	O(n)
Space	O(n)	O(n)	O(n)

Note: BST performance depends heavily on tree balance. Self-balancing trees (AVL, Red-Black) maintain O(log n) operations.

Tree Balancing Concepts

AVL Tree (Self-Balancing BST)

class AVLNode extends TreeNode {
  constructor(value) {
    super(value);
    this.height = 1;
  }
}

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

  getHeight(node) {
    return node ? node.height : 0;
  }

  getBalance(node) {
    return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  }

  updateHeight(node) {
    if (node) {
      node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
    }
  }

  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;

    // Perform rotation
    x.right = y;
    y.left = T2;

    // Update heights
    this.updateHeight(y);
    this.updateHeight(x);

    return x;
  }

  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;

    // Perform rotation
    y.left = x;
    x.right = T2;

    // Update heights
    this.updateHeight(x);
    this.updateHeight(y);

    return y;
  }

  insert(value) {
    this.root = this._insertRecursive(this.root, value);
  }

  _insertRecursive(node, value) {
    // Standard BST insertion
    if (!node) {
      return new AVLNode(value);
    }

    if (value < node.value) {
      node.left = this._insertRecursive(node.left, value);
    } else if (value > node.value) {
      node.right = this._insertRecursive(node.right, value);
    } else {
      return node; // Duplicates not allowed
    }

    // Update height
    this.updateHeight(node);

    // Get balance factor
    const balance = this.getBalance(node);

    // Left Left Case
    if (balance > 1 && value < node.left.value) {
      return this.rotateRight(node);
    }

    // Right Right Case
    if (balance < -1 && value > node.right.value) {
      return this.rotateLeft(node);
    }

    // Left Right Case
    if (balance > 1 && value > node.left.value) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }

    // Right Left Case
    if (balance < -1 && value < node.right.value) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }

    return node;
  }

  inOrder() {
    const result = [];
    this._inOrderRecursive(this.root, result);
    return result;
  }

  _inOrderRecursive(node, result) {
    if (node) {
      this._inOrderRecursive(node.left, result);
      result.push(node.value);
      this._inOrderRecursive(node.right, result);
    }
  }
}

// Usage
const avlTree = new AVLTree();
[10, 20, 30, 40, 50, 25].forEach(val => avlTree.insert(val));
console.log('AVL Tree (balanced):', avlTree.inOrder());

Advanced Binary Tree Operations

Tree Serialization and Deserialization

class TreeSerializer {
  // Serialize tree to string representation
  serialize(root) {
    if (!root) return 'null';

    const queue = [root];
    const result = [];

    while (queue.length > 0) {
      const node = queue.shift();

      if (node) {
        result.push(node.value);
        queue.push(node.left);
        queue.push(node.right);
      } else {
        result.push('null');
      }
    }

    // Remove trailing nulls
    while (result[result.length - 1] === 'null') {
      result.pop();
    }

    return result.join(',');
  }

  // Deserialize string back to tree
  deserialize(data) {
    if (!data || data === 'null') return null;

    const values = data.split(',');
    if (values.length === 0) return null;

    const root = new TreeNode(parseInt(values[0]));
    const queue = [root];
    let i = 1;

    while (queue.length > 0 && i < values.length) {
      const node = queue.shift();

      // Process left child
      if (i < values.length && values[i] !== 'null') {
        node.left = new TreeNode(parseInt(values[i]));
        queue.push(node.left);
      }
      i++;

      // Process right child
      if (i < values.length && values[i] !== 'null') {
        node.right = new TreeNode(parseInt(values[i]));
        queue.push(node.right);
      }
      i++;
    }

    return root;
  }
}

// Usage
const serializer = new TreeSerializer();
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));

const serialized = serializer.serialize(bst.root);
console.log('Serialized:', serialized);

const deserializedRoot = serializer.deserialize(serialized);
const deserializedTree = new BinarySearchTree();
deserializedTree.root = deserializedRoot;
console.log('Deserialized:', deserializedTree.getSortedValues());

Tree Validation and Properties

class TreeValidator {
  // Check if a binary tree is a valid BST
  isValidBST(root, min = -Infinity, max = Infinity) {
    if (!root) return true;

    if (root.value <= min || root.value >= max) {
      return false;
    }

    return this.isValidBST(root.left, min, root.value) &&
           this.isValidBST(root.right, root.value, max);
  }

  // Check if tree is balanced (height difference <= 1)
  isBalanced(root) {
    return this.checkBalance(root) !== -1;
  }

  checkBalance(node) {
    if (!node) return 0;

    const leftHeight = this.checkBalance(node.left);
    if (leftHeight === -1) return -1;

    const rightHeight = this.checkBalance(node.right);
    if (rightHeight === -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) {
      return -1;
    }

    return Math.max(leftHeight, rightHeight) + 1;
  }

  // Check if tree is complete (all levels filled except possibly last)
  isComplete(root) {
    if (!root) return true;

    const queue = [root];
    let foundNull = false;

    while (queue.length > 0) {
      const node = queue.shift();

      if (!node) {
        foundNull = true;
      } else {
        if (foundNull) return false; // Found node after null

        queue.push(node.left);
        queue.push(node.right);
      }
    }

    return true;
  }

  // Find diameter of tree (longest path between any two nodes)
  getDiameter(root) {
    let diameter = 0;

    const getDepth = (node) => {
      if (!node) return 0;

      const leftDepth = getDepth(node.left);
      const rightDepth = getDepth(node.right);

      // Update diameter if path through current node is longer
      diameter = Math.max(diameter, leftDepth + rightDepth);

      return Math.max(leftDepth, rightDepth) + 1;
    };

    getDepth(root);
    return diameter;
  }

  // Find lowest common ancestor
  findLCA(root, p, q) {
    if (!root || root.value === p || root.value === q) {
      return root;
    }

    const left = this.findLCA(root.left, p, q);
    const right = this.findLCA(root.right, p, q);

    if (left && right) return root;
    return left || right;
  }
}

// Usage
const validator = new TreeValidator();
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));

console.log('Is valid BST:', validator.isValidBST(bst.root)); // true
console.log('Is balanced:', validator.isBalanced(bst.root)); // true
console.log('Tree diameter:', validator.getDiameter(bst.root)); // 4
console.log('LCA of 20 and 40:', validator.findLCA(bst.root, 20, 40)?.value); // 30

Performance Optimization Tips

1. Iterative vs Recursive Approaches

class OptimizedTree {
  // Iterative in-order traversal (saves stack space)
  inOrderIterative(root) {
    const result = [];
    const stack = [];
    let current = root;

    while (current || stack.length > 0) {
      // Go to leftmost node
      while (current) {
        stack.push(current);
        current = current.left;
      }

      // Current is null, pop from stack
      current = stack.pop();
      result.push(current.value);

      // Move to right subtree
      current = current.right;
    }

    return result;
  }

  // Iterative level-order with early termination
  findLevel(root, target) {
    if (!root) return -1;

    const queue = [{ node: root, level: 0 }];

    while (queue.length > 0) {
      const { node, level } = queue.shift();

      if (node.value === target) {
        return level;
      }

      if (node.left) queue.push({ node: node.left, level: level + 1 });
      if (node.right) queue.push({ node: node.right, level: level + 1 });
    }

    return -1;
  }

  // Morris traversal (O(1) space complexity)
  morrisInOrder(root) {
    const result = [];
    let current = root;

    while (current) {
      if (!current.left) {
        result.push(current.value);
        current = current.right;
      } else {
        // Find predecessor
        let predecessor = current.left;
        while (predecessor.right && predecessor.right !== current) {
          predecessor = predecessor.right;
        }

        if (!predecessor.right) {
          // Make current the right child of predecessor
          predecessor.right = current;
          current = current.left;
        } else {
          // Revert the changes
          predecessor.right = null;
          result.push(current.value);
          current = current.right;
        }
      }
    }

    return result;
  }
}

Common Interview Problems

1. Path Sum Problems

class PathProblems {
  // Check if there's a path with given sum
  hasPathSum(root, targetSum) {
    if (!root) return false;

    if (!root.left && !root.right) {
      return root.value === targetSum;
    }

    const remainingSum = targetSum - root.value;
    return this.hasPathSum(root.left, remainingSum) ||
           this.hasPathSum(root.right, remainingSum);
  }

  // Find all paths with given sum
  findAllPaths(root, targetSum) {
    const paths = [];
    const currentPath = [];

    const dfs = (node, remainingSum) => {
      if (!node) return;

      currentPath.push(node.value);

      if (!node.left && !node.right && remainingSum === node.value) {
        paths.push([...currentPath]);
      }

      dfs(node.left, remainingSum - node.value);
      dfs(node.right, remainingSum - node.value);

      currentPath.pop(); // Backtrack
    };

    dfs(root, targetSum);
    return paths;
  }

  // Maximum path sum (path can start and end at any nodes)
  maxPathSum(root) {
    let maxSum = -Infinity;

    const maxPathSumHelper = (node) => {
      if (!node) return 0;

      const leftSum = Math.max(0, maxPathSumHelper(node.left));
      const rightSum = Math.max(0, maxPathSumHelper(node.right));

      // Path sum including current node as highest point
      const currentSum = node.value + leftSum + rightSum;
      maxSum = Math.max(maxSum, currentSum);

      // Return max path sum going through current node
      return node.value + Math.max(leftSum, rightSum);
    };

    maxPathSumHelper(root);
    return maxSum;
  }
}

2. Tree Construction Problems

class TreeConstruction {
  // Build tree from inorder and preorder traversals
  buildTreeFromTraversals(preorder, inorder) {
    if (preorder.length === 0 || inorder.length === 0) return null;

    const rootValue = preorder[0];
    const root = new TreeNode(rootValue);

    const rootIndex = inorder.indexOf(rootValue);

    // Split arrays
    const leftInorder = inorder.slice(0, rootIndex);
    const rightInorder = inorder.slice(rootIndex + 1);
    const leftPreorder = preorder.slice(1, leftInorder.length + 1);
    const rightPreorder = preorder.slice(leftInorder.length + 1);

    root.left = this.buildTreeFromTraversals(leftPreorder, leftInorder);
    root.right = this.buildTreeFromTraversals(rightPreorder, rightInorder);

    return root;
  }

  // Convert sorted array to balanced BST
  sortedArrayToBST(nums) {
    if (nums.length === 0) return null;

    const mid = Math.floor(nums.length / 2);
    const root = new TreeNode(nums[mid]);

    root.left = this.sortedArrayToBST(nums.slice(0, mid));
    root.right = this.sortedArrayToBST(nums.slice(mid + 1));

    return root;
  }
}

// Usage
const constructor = new TreeConstruction();
const sortedArray = [1, 2, 3, 4, 5, 6, 7];
const balancedBST = constructor.sortedArrayToBST(sortedArray);

const tree = new BinaryTree();
tree.root = balancedBST;
console.log('Balanced BST from array:', tree.levelOrderTraversal());

Best Practices and Performance Tips

1. Memory Management

class MemoryEfficientTree {
  constructor() {
    this.root = null;
    this.nodePool = []; // Object pooling to reduce GC pressure
  }

  createNode(value) {
    if (this.nodePool.length > 0) {
      const node = this.nodePool.pop();
      node.value = value;
      node.left = null;
      node.right = null;
      return node;
    }
    return new TreeNode(value);
  }

  recycleNode(node) {
    if (node) {
      this.nodePool.push(node);
    }
  }

  // Clean up tree and recycle nodes
  clear() {
    this.clearRecursive(this.root);
    this.root = null;
  }

  clearRecursive(node) {
    if (node) {
      this.clearRecursive(node.left);
      this.clearRecursive(node.right);
      this.recycleNode(node);
    }
  }
}

2. Batch Operations

class BatchTree extends BinarySearchTree {
  // Bulk insert for better performance
  bulkInsert(values) {
    // Sort values first for better balance
    const sortedValues = [...values].sort((a, b) => a - b);

    // Remove duplicates
    const uniqueValues = [...new Set(sortedValues)];

    this.root = this.buildBalancedTree(uniqueValues, 0, uniqueValues.length - 1);
  }

  buildBalancedTree(values, start, end) {
    if (start > end) return null;

    const mid = Math.floor((start + end) / 2);
    const node = new TreeNode(values[mid]);

    node.left = this.buildBalancedTree(values, start, mid - 1);
    node.right = this.buildBalancedTree(values, mid + 1, end);

    return node;
  }

  // Range search for efficient querying
  searchRange(min, max) {
    const result = [];
    this.searchRangeRecursive(this.root, min, max, result);
    return result;
  }

  searchRangeRecursive(node, min, max, result) {
    if (!node) return;

    if (node.value >= min && node.value <= max) {
      result.push(node.value);
    }

    if (node.value > min) {
      this.searchRangeRecursive(node.left, min, max, result);
    }

    if (node.value < max) {
      this.searchRangeRecursive(node.right, min, max, result);
    }
  }
}

// Usage
const batchTree = new BatchTree();
const largeDataset = Array.from({ length: 1000 }, (_, i) => Math.floor(Math.random() * 10000));

console.time('Bulk Insert');
batchTree.bulkInsert(largeDataset);
console.timeEnd('Bulk Insert');

console.log('Range 100-200:', batchTree.searchRange(100, 200));

Conclusion

Binary Trees are fundamental data structures that provide the foundation for many advanced algorithms and applications. From simple binary trees to self-balancing BSTs, from file systems to machine learning decision trees, understanding these structures is crucial for any developer.

Key Takeaways:

Binary Trees organize data hierarchically with at most two children per node
Binary Search Trees provide efficient O(log n) operations when balanced
Tree Traversals offer different ways to visit nodes: in-order, pre-order, post-order, and level-order
Self-balancing trees (AVL, Red-Black) maintain optimal performance automatically
Real-world applications include file systems, expression parsing, decision trees, and auto-complete
Performance considerations matter: choose the right implementation based on your use case

When to Use Binary Trees:

Hierarchical data representation (file systems, organizational charts)
Efficient searching with BSTs (databases, search engines)
Expression evaluation and parsing
Priority queues with heaps
Decision-making systems in AI/ML
Auto-complete and prefix matching with tries

Stay tuned for the next post in this series, where we'll explore Graphs and their algorithms!

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!

Data Structures Series #2: Queue - Implementation & Use Cases

Priyadharshini Selvaraj — Thu, 05 Jun 2025 07:28:57 +0000

Introduction

Welcome back to my tech blog series on data structures! Today, we're diving into Queues, another fundamental data structure that follows the First In, First Out (FIFO) principle. We'll implement queues in JavaScript, explore practical examples, and see how they power real-world applications.

What is a Queue?

A Queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning the first item added is the first one to be removed. Think of a line at a coffee shop—the first person in line gets served first, and new customers join at the back.

Key Operations in a Queue:

Enqueue – Adds an element to the rear (back) of the queue.
Dequeue – Removes an element from the front of the queue.
Front – Returns the front element without removing it.
Rear – Returns the rear element without removing it.
isEmpty – Checks if the queue is empty.
Size – Returns the number of elements in the queue.

Implementing a Queue in JavaScript

1. Using an Array (Simple but Inefficient)

While arrays can implement queues using push() and shift() methods, this approach has O(n) time complexity for dequeue operations due to array shifting.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.shift(); // O(n) operation
  }

  front() {
    return this.isEmpty() ? null : this.items[0];
  }

  rear() {
    return this.isEmpty() ? null : this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Usage example
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.front()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.size()); // 2

2. Using Two Pointers (Optimized Array Approach)

This approach maintains front and rear pointers to avoid the shifting overhead, providing O(1) operations.

class Queue {
  constructor() {
    this.items = [];
    this.frontIndex = 0;
    this.rearIndex = 0;
  }

  enqueue(element) {
    this.items[this.rearIndex] = element;
    this.rearIndex++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;

    // Reset indices when queue becomes empty
    if (this.frontIndex === this.rearIndex) {
      this.frontIndex = 0;
      this.rearIndex = 0;
    }

    return item;
  }

  front() {
    return this.isEmpty() ? null : this.items[this.frontIndex];
  }

  rear() {
    return this.isEmpty() ? null : this.items[this.rearIndex - 1];
  }

  isEmpty() {
    return this.frontIndex === this.rearIndex;
  }

  size() {
    return this.rearIndex - this.frontIndex;
  }
}

3. Using a Linked List (Most Efficient)

Linked list implementation provides O(1) operations for both enqueue and dequeue without memory waste.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);

    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }

    this.length++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }

    const dequeuedValue = this.front.value;
    this.front = this.front.next;

    if (!this.front) {
      this.rear = null; // Queue is now empty
    }

    this.length--;
    return dequeuedValue;
  }

  frontValue() {
    return this.isEmpty() ? null : this.front.value;
  }

  rearValue() {
    return this.isEmpty() ? null : this.rear.value;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }
}

// Usage example
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.frontValue()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.size()); // 2

Real-World Use Cases of Queues

1. Print Queue Management

Printers use queues to manage print jobs in the order they were received.

class PrintQueue {
  constructor() {
    this.queue = new Queue();
  }

  addPrintJob(document) {
    this.queue.enqueue({
      document,
      timestamp: new Date(),
      id: Math.random().toString(36).substr(2, 9)
    });
    console.log(`Print job added: ${document}`);
  }

  processPrintJob() {
    const job = this.queue.dequeue();
    if (job) {
      console.log(`Printing: ${job.document} (Added: ${job.timestamp})`);
      return job;
    }
    console.log('No print jobs in queue');
    return null;
  }

  getPendingJobs() {
    return this.queue.size();
  }
}

// Usage
const printer = new PrintQueue();
printer.addPrintJob('Report.pdf');
printer.addPrintJob('Invoice.docx');
printer.processPrintJob(); // Prints: Report.pdf

2. Breadth-First Search (BFS) in Graphs

BFS algorithm uses a queue to explore nodes level by level.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  bfs(start) {
    const queue = new Queue();
    const visited = {};
    const result = [];

    queue.enqueue(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
      const vertex = queue.dequeue();
      result.push(vertex);

      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.enqueue(neighbor);
        }
      });
    }

    return result;
  }
}

// Usage
const graph = new Graph();
['A', 'B', 'C', 'D', 'E'].forEach(v => graph.addVertex(v));
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');

console.log(graph.bfs('A')); // ['A', 'B', 'C', 'D', 'E']

3. Task Scheduling and Job Processing

Operating systems and web servers use queues for task scheduling and processing requests.

class TaskScheduler {
  constructor() {
    this.taskQueue = new Queue();
    this.isProcessing = false;
  }

  addTask(task) {
    this.taskQueue.enqueue({
      id: Math.random().toString(36).substr(2, 9),
      task,
      addedAt: Date.now()
    });

    if (!this.isProcessing) {
      this.processNextTask();
    }
  }

  async processNextTask() {
    if (this.taskQueue.isEmpty()) {
      this.isProcessing = false;
      return;
    }

    this.isProcessing = true;
    const taskItem = this.taskQueue.dequeue();

    console.log(`Processing task: ${taskItem.id}`);

    try {
      await taskItem.task();
      console.log(`Task completed: ${taskItem.id}`);
    } catch (error) {
      console.error(`Task failed: ${taskItem.id}`, error);
    }

    // Process next task
    setTimeout(() => this.processNextTask(), 100);
  }

  getPendingTasks() {
    return this.taskQueue.size();
  }
}

// Usage
const scheduler = new TaskScheduler();

scheduler.addTask(() => new Promise(resolve => {
  setTimeout(() => {
    console.log('Sending email...');
    resolve();
  }, 1000);
}));

scheduler.addTask(() => new Promise(resolve => {
  setTimeout(() => {
    console.log('Processing payment...');
    resolve();
  }, 500);
}));

4. Buffer for Data Streams

Queues act as buffers in streaming applications, handling data flow between producers and consumers.

class StreamBuffer {
  constructor(maxSize = 10) {
    this.buffer = new Queue();
    this.maxSize = maxSize;
    this.consumers = [];
  }

  // Producer adds data
  produce(data) {
    if (this.buffer.size() >= this.maxSize) {
      console.log('Buffer full, dropping oldest data');
      this.buffer.dequeue(); // Drop oldest
    }

    this.buffer.enqueue({
      data,
      timestamp: Date.now()
    });

    this.notifyConsumers();
  }

  // Consumer subscribes to data
  subscribe(callback) {
    this.consumers.push(callback);
  }

  notifyConsumers() {
    if (!this.buffer.isEmpty()) {
      const item = this.buffer.dequeue();
      this.consumers.forEach(callback => callback(item));
    }
  }

  getBufferStatus() {
    return {
      size: this.buffer.size(),
      maxSize: this.maxSize,
      utilization: (this.buffer.size() / this.maxSize * 100).toFixed(1) + '%'
    };
  }
}

// Usage
const streamBuffer = new StreamBuffer(5);

// Subscribe a consumer
streamBuffer.subscribe(item => {
  console.log(`Consuming: ${item.data} (${new Date(item.timestamp)})`);
});

// Produce data
setInterval(() => {
  streamBuffer.produce(`Data packet ${Math.floor(Math.random() * 100)}`);
}, 2000);

5. Web Server Request Handling

Web servers use queues to manage incoming HTTP requests during high traffic.

class WebServerQueue {
  constructor(maxConcurrent = 3) {
    this.requestQueue = new Queue();
    this.activeRequests = 0;
    this.maxConcurrent = maxConcurrent;
  }

  handleRequest(request) {
    this.requestQueue.enqueue({
      ...request,
      receivedAt: Date.now(),
      id: Math.random().toString(36).substr(2, 9)
    });

    this.processQueue();
  }

  async processQueue() {
    if (this.activeRequests >= this.maxConcurrent || this.requestQueue.isEmpty()) {
      return;
    }

    this.activeRequests++;
    const request = this.requestQueue.dequeue();

    console.log(`Processing request ${request.id}: ${request.method} ${request.url}`);

    try {
      // Simulate request processing
      await new Promise(resolve => setTimeout(resolve, Math.random() * 2000));
      console.log(`Request ${request.id} completed successfully`);
    } catch (error) {
      console.error(`Request ${request.id} failed:`, error);
    } finally {
      this.activeRequests--;
      this.processQueue(); // Process next request
    }
  }

  getQueueStatus() {
    return {
      pending: this.requestQueue.size(),
      active: this.activeRequests,
      maxConcurrent: this.maxConcurrent
    };
  }
}

// Usage
const server = new WebServerQueue(2);

// Simulate incoming requests
const requests = [
  { method: 'GET', url: '/api/users' },
  { method: 'POST', url: '/api/orders' },
  { method: 'GET', url: '/api/products' },
  { method: 'PUT', url: '/api/users/123' },
  { method: 'DELETE', url: '/api/orders/456' }
];

requests.forEach((req, index) => {
  setTimeout(() => server.handleRequest(req), index * 500);
});

Queue Variants

Circular Queue

A circular queue uses a fixed-size array where the rear wraps around to the beginning when it reaches the end.

class CircularQueue {
  constructor(size) {
    this.items = new Array(size);
    this.maxSize = size;
    this.front = -1;
    this.rear = -1;
    this.currentSize = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error('Queue is full');
    }

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    } else {
      this.rear = (this.rear + 1) % this.maxSize;
    }

    this.items[this.rear] = element;
    this.currentSize++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }

    const item = this.items[this.front];
    this.items[this.front] = null;

    if (this.currentSize === 1) {
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.maxSize;
    }

    this.currentSize--;
    return item;
  }

  isFull() {
    return this.currentSize === this.maxSize;
  }

  isEmpty() {
    return this.currentSize === 0;
  }

  size() {
    return this.currentSize;
  }
}

Priority Queue

A priority queue where elements are dequeued based on priority rather than insertion order.

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;

    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }

  dequeue() {
    return this.isEmpty() ? null : this.items.shift().element;
  }

  front() {
    return this.isEmpty() ? null : this.items[0].element;
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Usage - Lower numbers have higher priority
const pq = new PriorityQueue();
pq.enqueue('Low priority task', 3);
pq.enqueue('High priority task', 1);
pq.enqueue('Medium priority task', 2);

console.log(pq.dequeue()); // 'High priority task'
console.log(pq.dequeue()); // 'Medium priority task'

Time and Space Complexity

Operation	Array (Simple)	Array (Two Pointers)	Linked List
Enqueue	O(1)	O(1)	O(1)
Dequeue	O(n)	O(1)	O(1)
Front	O(1)	O(1)	O(1)
Space	O(n)	O(n)	O(n)

Best Implementation: Linked List provides the most consistent O(1) performance for all operations.

Conclusion

Queues are essential data structures that power many real-world applications, from task scheduling and web server request handling to graph algorithms and data streaming. Understanding their FIFO behavior and various implementations will help you choose the right approach for your specific use case.

The key takeaways:

Use linked list implementation for optimal performance
Circular queues for fixed-size scenarios
Priority queues when order matters more than insertion time
Queues excel in producer-consumer patterns and breadth-first processing

Stay tuned for the next post in this series, where we'll explore Binary Trees!

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!

Data Structures Series #1: Stacks - Implementation & Use Cases

Priyadharshini Selvaraj — Sun, 23 Feb 2025 11:46:19 +0000

Introduction

Welcome to my tech blog series, where I'll explore one data structure a day! In this first post, we’ll dive into Stacks, one of the fundamental data structures in computer science. We’ll cover its implementation in JavaScript, explore real-world use cases, and provide example code to reinforce your understanding.

What is a Stack?

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last item added is the first one to be removed. Think of a stack of plates in a cafeteria—each new plate is placed on top, and you take the top plate first.

Key Operations in a Stack:

Push – Adds an element to the top of the stack.
Pop – Removes the top element from the stack.
Peek – Returns the top element without removing it.
isEmpty – Checks if the stack is empty.
Size – Returns the number of elements in the stack.

Implementing a Stack in JavaScript

1. Using an Array (Simplest Approach)

JavaScript arrays have built-in methods (push and pop) that make it easy to implement a stack.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.pop();
  }

  peek() {
    return this.isEmpty() ? null : this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Usage example
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop());  // 20
console.log(stack.size()); // 1

2. Using a Linked List (More Efficient for Large Data Sets)

For a more efficient stack (especially for large-scale applications), we can implement it using a linked list, avoiding array resizing overhead.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.length--;
    return poppedValue;
  }

  peek() {
    return this.isEmpty() ? null : this.top.value;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }
}

// Usage example
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop());  // 20
console.log(stack.size()); // 1

Real-World Use Cases of Stacks

1. Browser History Navigation

When you visit a webpage, it gets pushed onto a stack. Pressing the back button pops the last visited page.

class BrowserHistory {
  constructor() {
    this.history = new Stack();
  }

  visitPage(url) {
    this.history.push(url);
  }

  goBack() {
    return this.history.pop();
  }
}

const browser = new BrowserHistory();
browser.visitPage('google.com');
browser.visitPage('dev.to');
console.log(browser.goBack()); // dev.to

2. Undo/Redo Functionality

Text editors use two stacks—one for undo and one for redo actions.

3. Expression Evaluation - Postfix, Prefix

Stacks are used to evaluate expressions like Postfix (Reverse Polish Notation) and Prefix Notation.

function evaluatePostfix(expression) {
  const stack = new Stack();
  const tokens = expression.split(' ');

  for (let token of tokens) {
    if (!isNaN(token)) {
      stack.push(parseInt(token));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(a / b); break;
      }
    }
  }
  return stack.pop();
}

console.log(evaluatePostfix("2 3 + 5 *")); // 25

4. Expression Evaluation - Syntax Parsing

Stacks are used in evaluating arithmetic expressions and validating balanced parentheses in expressions like:

function isBalanced(expression) {
  const stack = [];
  const pairs = { '(': ')', '{': '}', '[': ']' };

  for (let char of expression) {
    if (pairs[char]) {
      stack.push(char);
    } else if (Object.values(pairs).includes(char)) {
      if (!stack.length || pairs[stack.pop()] !== char) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

console.log(isBalanced("( [ { } ] )")); // true
console.log(isBalanced("( [ { ] } )")); // false

5. Backtracking Algorithms

Stacks are essential for solving problems using backtracking, such as maze solving, depth-first search (DFS) in graphs, etc.

Conclusion

Stacks are a fundamental data structure that power many real-world applications, from browser history management to expression evaluation. By understanding their implementation in JavaScript and their use cases, you’ll be well-equipped to use them effectively in your projects.

Stay tuned for the next post in this series, where we’ll explore Queues!

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!

DEV Community: Priyadharshini Selvaraj

Mastering JavaScript Internals#2 The Parser & AST

The Parser: How JavaScript Actually Reads Your Code

🗺️ The Big Picture: 3 Steps Before Execution

Step 1: Tokenizing — Breaking Code into Pieces

Step 2: Parsing — Building the Tree (AST)

🚀 Lazy vs. Eager Parsing: A Smart Shortcut

❌ When Parsing Goes Wrong: Syntax Errors

🛠️ You Can See the AST Yourself

📝 Quick Recap

➡️ Up Next

🔗 Connect with Me

Mastering JavaScript Internals #1 - Introduction

Why "I Know JavaScript" Isn't Enough Anymore

🤔 The Gap Most Developers Don't Know Exists

🧱 The 6 Things We'll Cover

1. 🔍 How the Engine Reads Your Code

2. ⚡ Why JavaScript Gets Faster the More It Runs

3. 🧠 Where Your Data Actually Lives

4. 🔗 How Scope, this, and Prototypes Actually Work

5. 🔄 The Event Loop (the Real Version)

6. 📦 Modules, Bundlers & Performance

📋 What to Expect from Each Post

✅ What You'll Be Able to Do After This Series

➡️ Up Next

🔗 Connect with Me

Data Structures Series #4: Graphs - Implementation & Use Cases

Introduction

What is a Graph?

Key Terminology

Implementing a Graph in JavaScript

Basic Graph Class

Graph Traversals

1. Depth-First Search (DFS)

2. Breadth-First Search (BFS)

DFS vs BFS — Quick Comparison

Real-World Use Cases

Time and Space Complexity

Conclusion

🔗 Connect with Me

RAG and LangChain Basics

Introduction

What is RAG?

Traditional LLM vs RAG Architecture

RAG System Architecture

1. Indexing Phase (Data Preparation)

2. Retrieval Phase (Query Processing)

Enter LangChain

Core LangChain Components for RAG

Building a RAG System with LangChain

Step 1: Document Ingestion and Processing

Step 2: Setting up the Retrieval Chain

RAG Query Flow Visualization

Advanced RAG Patterns

1. Multi-Query Retrieval

2. Contextual Compression

3. Self-Query Retrieval

Best Practices for Production RAG Systems

Data Quality and Chunking Strategy

Retrieval Optimization

Performance Considerations

Real-World Applications

Conclusion

Data Structures Series #3: Binary Trees - Implementation & Use Cases

Introduction

What is a Binary Tree?

Key Terminology:

Basic Binary Tree Implementation

Binary Tree Traversal Methods

1. Depth-First Search (DFS) Traversals

2. Breadth-First Search (BFS) - Level Order Traversal

Binary Search Tree (BST)

Real-World Use Cases of Binary Trees

1. File System Directory Structure

2. Expression Tree for Mathematical Expressions

3. Decision Tree for AI/ML Applications

4. Auto-Complete/Search Suggestions (Trie Tree)

5. Heap Implementation using Binary Tree

Time and Space Complexity

Tree Balancing Concepts

4. 🔗 How Scope, `this`, and Prototypes Actually Work