JavaScript Data Structures - Complete Guide to Arrays, Objects, Maps, Sets

Data structures are fundamental to efficient programming. JavaScript provides built-in data structures like arrays and objects, as well as newer additions like Map and Set. This guide covers all essential data structures with practical implementations.

Built-in Data Structures

Arrays - Dynamic Lists

Arrays are ordered collections that can store any type of data and provide numerous methods for manipulation.

// Array creation and basic operations
class AdvancedArray {
  constructor(data = []) {
    this.data = [...data];
  }

  // Add elements
  push(...elements) {
    this.data.push(...elements);
    return this;
  }

  unshift(...elements) {
    this.data.unshift(...elements);
    return this;
  }

  // Remove elements
  pop() {
    return this.data.pop();
  }

  shift() {
    return this.data.shift();
  }

  // Remove by index
  removeAt(index) {
    return this.data.splice(index, 1)[0];
  }

  // Remove by value
  remove(value) {
    const index = this.data.indexOf(value);
    return index !== -1 ? this.removeAt(index) : undefined;
  }

  // Remove all occurrences
  removeAll(value) {
    this.data = this.data.filter((item) => item !== value);
    return this;
  }

  // Insert at specific position
  insertAt(index, ...elements) {
    this.data.splice(index, 0, ...elements);
    return this;
  }

  // Find elements
  find(predicate) {
    return this.data.find(predicate);
  }

  findIndex(predicate) {
    return this.data.findIndex(predicate);
  }

  findAll(predicate) {
    return this.data.filter(predicate);
  }

  // Array transformations
  map(callback) {
    return new AdvancedArray(this.data.map(callback));
  }

  filter(predicate) {
    return new AdvancedArray(this.data.filter(predicate));
  }

  reduce(callback, initialValue) {
    return this.data.reduce(callback, initialValue);
  }

  // Sorting
  sort(compareFunction) {
    this.data.sort(compareFunction);
    return this;
  }

  sortBy(keyFunction) {
    this.data.sort((a, b) => {
      const aKey = keyFunction(a);
      const bKey = keyFunction(b);

      if (aKey < bKey) return -1;
      if (aKey > bKey) return 1;
      return 0;
    });
    return this;
  }

  // Grouping
  groupBy(keyFunction) {
    return this.data.reduce((groups, item) => {
      const key = keyFunction(item);
      if (!groups[key]) groups[key] = [];
      groups[key].push(item);
      return groups;
    }, {});
  }

  // Chunking
  chunk(size) {
    const chunks = [];
    for (let i = 0; i < this.data.length; i += size) {
      chunks.push(this.data.slice(i, i + size));
    }
    return chunks;
  }

  // Unique elements
  unique() {
    return new AdvancedArray([...new Set(this.data)]);
  }

  uniqueBy(keyFunction) {
    const seen = new Set();
    const result = [];

    for (const item of this.data) {
      const key = keyFunction(item);
      if (!seen.has(key)) {
        seen.add(key);
        result.push(item);
      }
    }

    return new AdvancedArray(result);
  }

  // Array operations
  intersection(other) {
    const otherSet = new Set(other);
    return new AdvancedArray(this.data.filter((item) => otherSet.has(item)));
  }

  union(other) {
    return new AdvancedArray([...new Set([...this.data, ...other])]);
  }

  difference(other) {
    const otherSet = new Set(other);
    return new AdvancedArray(this.data.filter((item) => !otherSet.has(item)));
  }

  // Utilities
  get length() {
    return this.data.length;
  }

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

  clone() {
    return new AdvancedArray(this.data);
  }

  toArray() {
    return [...this.data];
  }

  toString() {
    return this.data.toString();
  }

  // Iterator support
  [Symbol.iterator]() {
    return this.data[Symbol.iterator]();
  }
}

// Usage examples
const numbers = new AdvancedArray([1, 2, 3, 4, 5, 3, 2, 1]);

console.log(numbers.unique().toArray()); // [1, 2, 3, 4, 5]
console.log(numbers.groupBy((x) => (x % 2 === 0 ? 'even' : 'odd')));
console.log(numbers.chunk(3)); // [[1, 2, 3], [4, 5, 3], [2, 1]]

const people = new AdvancedArray([
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 35 },
]);

console.log(people.sortBy((person) => person.age).toArray());
console.log(people.find((person) => person.age > 30));

Objects - Key-Value Pairs

Objects are fundamental data structures in JavaScript, providing key-value mapping with string keys.

// Enhanced object utilities
class AdvancedObject {
  constructor(data = {}) {
    this.data = { ...data };
  }

  // Get and set operations
  get(key, defaultValue = undefined) {
    return this.has(key) ? this.data[key] : defaultValue;
  }

  set(key, value) {
    this.data[key] = value;
    return this;
  }

  setIfAbsent(key, value) {
    if (!this.has(key)) {
      this.data[key] = value;
    }
    return this;
  }

  // Nested operations
  getDeep(path, defaultValue = undefined) {
    const keys = path.split('.');
    let current = this.data;

    for (const key of keys) {
      if (current && typeof current === 'object' && key in current) {
        current = current[key];
      } else {
        return defaultValue;
      }
    }

    return current;
  }

  setDeep(path, value) {
    const keys = path.split('.');
    let current = this.data;

    for (let i = 0; i < keys.length - 1; i++) {
      const key = keys[i];
      if (!(key in current) || typeof current[key] !== 'object') {
        current[key] = {};
      }
      current = current[key];
    }

    current[keys[keys.length - 1]] = value;
    return this;
  }

  // Existence checks
  has(key) {
    return key in this.data;
  }

  hasDeep(path) {
    try {
      const value = this.getDeep(path);
      return value !== undefined;
    } catch {
      return false;
    }
  }

  // Deletion
  delete(key) {
    const existed = this.has(key);
    delete this.data[key];
    return existed;
  }

  // Keys, values, entries
  keys() {
    return Object.keys(this.data);
  }

  values() {
    return Object.values(this.data);
  }

  entries() {
    return Object.entries(this.data);
  }

  // Transformations
  map(callback) {
    const result = {};
    for (const [key, value] of this.entries()) {
      const [newKey, newValue] = callback(value, key);
      result[newKey] = newValue;
    }
    return new AdvancedObject(result);
  }

  filter(predicate) {
    const result = {};
    for (const [key, value] of this.entries()) {
      if (predicate(value, key)) {
        result[key] = value;
      }
    }
    return new AdvancedObject(result);
  }

  // Merging
  merge(...objects) {
    for (const obj of objects) {
      Object.assign(this.data, obj);
    }
    return this;
  }

  deepMerge(...objects) {
    for (const obj of objects) {
      this._deepMergeObject(this.data, obj);
    }
    return this;
  }

  _deepMergeObject(target, source) {
    for (const key in source) {
      if (
        source[key] &&
        typeof source[key] === 'object' &&
        !Array.isArray(source[key])
      ) {
        if (!target[key] || typeof target[key] !== 'object') {
          target[key] = {};
        }
        this._deepMergeObject(target[key], source[key]);
      } else {
        target[key] = source[key];
      }
    }
  }

  // Cloning
  clone() {
    return new AdvancedObject(this.data);
  }

  deepClone() {
    return new AdvancedObject(JSON.parse(JSON.stringify(this.data)));
  }

  // Utilities
  size() {
    return this.keys().length;
  }

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

  clear() {
    this.data = {};
    return this;
  }

  toObject() {
    return { ...this.data };
  }
}

// Usage examples
const config = new AdvancedObject({
  app: {
    name: 'MyApp',
    version: '1.0.0',
    features: {
      auth: true,
      notifications: false,
    },
  },
  database: {
    host: 'localhost',
    port: 5432,
  },
});

console.log(config.getDeep('app.features.auth')); // true
config.setDeep('app.features.logging', true);
console.log(config.hasDeep('database.ssl')); // false

const filtered = config.filter((value, key) => key.startsWith('app'));
console.log(filtered.toObject());

Maps - Key-Value with Any Key Type

Maps provide key-value storage where keys can be of any type, including objects and primitives.

// Enhanced Map implementation
class AdvancedMap extends Map {
  constructor(iterable) {
    super(iterable);
  }

  // Enhanced get with default
  getOrDefault(key, defaultValue) {
    return this.has(key) ? this.get(key) : defaultValue;
  }

  // Set if absent
  setIfAbsent(key, value) {
    if (!this.has(key)) {
      this.set(key, value);
    }
    return this;
  }

  // Compute value if absent
  computeIfAbsent(key, computeFunction) {
    if (!this.has(key)) {
      this.set(key, computeFunction(key));
    }
    return this.get(key);
  }

  // Update existing value
  computeIfPresent(key, updateFunction) {
    if (this.has(key)) {
      this.set(key, updateFunction(key, this.get(key)));
    }
    return this;
  }

  // Transformations
  map(callback) {
    const result = new AdvancedMap();
    for (const [key, value] of this) {
      const [newKey, newValue] = callback(value, key);
      result.set(newKey, newValue);
    }
    return result;
  }

  filter(predicate) {
    const result = new AdvancedMap();
    for (const [key, value] of this) {
      if (predicate(value, key)) {
        result.set(key, value);
      }
    }
    return result;
  }

  reduce(callback, initialValue) {
    let accumulator = initialValue;
    for (const [key, value] of this) {
      accumulator = callback(accumulator, value, key);
    }
    return accumulator;
  }

  // Utilities
  keyArray() {
    return Array.from(this.keys());
  }

  valueArray() {
    return Array.from(this.values());
  }

  entryArray() {
    return Array.from(this.entries());
  }

  // Find operations
  findKey(predicate) {
    for (const [key, value] of this) {
      if (predicate(value, key)) {
        return key;
      }
    }
    return undefined;
  }

  findValue(predicate) {
    for (const [key, value] of this) {
      if (predicate(value, key)) {
        return value;
      }
    }
    return undefined;
  }

  // Group operations
  static groupBy(iterable, keyFunction) {
    const map = new AdvancedMap();
    for (const item of iterable) {
      const key = keyFunction(item);
      if (!map.has(key)) {
        map.set(key, []);
      }
      map.get(key).push(item);
    }
    return map;
  }

  // Merging
  merge(other) {
    for (const [key, value] of other) {
      this.set(key, value);
    }
    return this;
  }

  // Clone
  clone() {
    return new AdvancedMap(this);
  }

  // Invert (swap keys and values)
  invert() {
    const result = new AdvancedMap();
    for (const [key, value] of this) {
      result.set(value, key);
    }
    return result;
  }
}

// Usage examples
const userCache = new AdvancedMap();

// Object keys
const user1 = { id: 1, name: 'Alice' };
const user2 = { id: 2, name: 'Bob' };

userCache.set(user1, 'cached_data_1');
userCache.set(user2, 'cached_data_2');

console.log(userCache.get(user1)); // 'cached_data_1'

// Grouping example
const items = [
  { category: 'fruit', name: 'apple' },
  { category: 'fruit', name: 'banana' },
  { category: 'vegetable', name: 'carrot' },
];

const grouped = AdvancedMap.groupBy(items, (item) => item.category);
console.log(grouped.get('fruit')); // [{ category: 'fruit', name: 'apple' }, ...]

Sets - Unique Value Collections

Sets store unique values and provide efficient membership testing.

// Enhanced Set implementation
class AdvancedSet extends Set {
  constructor(iterable) {
    super(iterable);
  }

  // Set operations
  union(other) {
    return new AdvancedSet([...this, ...other]);
  }

  intersection(other) {
    return new AdvancedSet([...this].filter((x) => other.has(x)));
  }

  difference(other) {
    return new AdvancedSet([...this].filter((x) => !other.has(x)));
  }

  symmetricDifference(other) {
    const union = this.union(other);
    const intersection = this.intersection(other);
    return union.difference(intersection);
  }

  // Subset operations
  isSubsetOf(other) {
    return [...this].every((x) => other.has(x));
  }

  isSupersetOf(other) {
    return [...other].every((x) => this.has(x));
  }

  isDisjointWith(other) {
    return this.intersection(other).size === 0;
  }

  // Transformations
  map(callback) {
    return new AdvancedSet([...this].map(callback));
  }

  filter(predicate) {
    return new AdvancedSet([...this].filter(predicate));
  }

  reduce(callback, initialValue) {
    return [...this].reduce(callback, initialValue);
  }

  // Find operations
  find(predicate) {
    for (const value of this) {
      if (predicate(value)) {
        return value;
      }
    }
    return undefined;
  }

  // Utilities
  toArray() {
    return [...this];
  }

  first() {
    return this.values().next().value;
  }

  last() {
    const arr = this.toArray();
    return arr[arr.length - 1];
  }

  random() {
    const arr = this.toArray();
    return arr[Math.floor(Math.random() * arr.length)];
  }

  // Partitioning
  partition(predicate) {
    const truthy = new AdvancedSet();
    const falsy = new AdvancedSet();

    for (const value of this) {
      if (predicate(value)) {
        truthy.add(value);
      } else {
        falsy.add(value);
      }
    }

    return [truthy, falsy];
  }

  // Clone
  clone() {
    return new AdvancedSet(this);
  }
}

// Usage examples
const set1 = new AdvancedSet([1, 2, 3, 4]);
const set2 = new AdvancedSet([3, 4, 5, 6]);

console.log(set1.union(set2).toArray()); // [1, 2, 3, 4, 5, 6]
console.log(set1.intersection(set2).toArray()); // [3, 4]
console.log(set1.difference(set2).toArray()); // [1, 2]

const [evens, odds] = set1.partition((x) => x % 2 === 0);
console.log(evens.toArray()); // [2, 4]
console.log(odds.toArray()); // [1, 3]

Custom Data Structures

Stack - LIFO (Last In, First Out)

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

  // Add element to top
  push(element) {
    this.items.push(element);
    return this;
  }

  // Remove and return top element
  pop() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    return this.items.pop();
  }

  // View top element without removing
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }

  // Check if stack is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // Get stack size
  size() {
    return this.items.length;
  }

  // Clear stack
  clear() {
    this.items = [];
    return this;
  }

  // Convert to array
  toArray() {
    return [...this.items];
  }

  // String representation
  toString() {
    return this.items.toString();
  }
}

// Stack with maximum size
class BoundedStack extends Stack {
  constructor(maxSize) {
    super();
    this.maxSize = maxSize;
  }

  push(element) {
    if (this.size() >= this.maxSize) {
      throw new Error('Stack overflow');
    }
    return super.push(element);
  }

  isFull() {
    return this.size() >= this.maxSize;
  }
}

// Usage examples
const stack = new Stack();
stack.push(1).push(2).push(3);

console.log(stack.peek()); // 3
console.log(stack.pop()); // 3
console.log(stack.size()); // 2

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

  for (const token of tokens) {
    if (isNumber(token)) {
      stack.push(parseFloat(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;
        default:
          throw new Error(`Unknown operator: ${token}`);
      }
    }
  }

  return stack.pop();
}

function isNumber(str) {
  return !isNaN(parseFloat(str)) && isFinite(str);
}

console.log(evaluatePostfix('15 7 1 1 + - * 3 +')); // 54

Queue - FIFO (First In, First Out)

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

  // Add element to rear
  enqueue(element) {
    this.items.push(element);
    return this;
  }

  // Remove and return front element
  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }

    const element = this.items[this.front];
    this.front++;

    // Reset when queue becomes empty
    if (this.front === this.items.length) {
      this.items = [];
      this.front = 0;
    }

    return element;
  }

  // View front element without removing
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.front];
  }

  // Check if queue is empty
  isEmpty() {
    return this.front === this.items.length;
  }

  // Get queue size
  size() {
    return this.items.length - this.front;
  }

  // Clear queue
  clear() {
    this.items = [];
    this.front = 0;
    return this;
  }

  // Convert to array
  toArray() {
    return this.items.slice(this.front);
  }

  // String representation
  toString() {
    return this.toArray().toString();
  }
}

// Priority Queue
class PriorityQueue {
  constructor(compareFunction = (a, b) => a.priority - b.priority) {
    this.items = [];
    this.compare = compareFunction;
  }

  enqueue(element, priority = 0) {
    const item = { element, priority };

    // Find correct position to insert
    let insertIndex = this.items.length;
    for (let i = 0; i < this.items.length; i++) {
      if (this.compare(item, this.items[i]) < 0) {
        insertIndex = i;
        break;
      }
    }

    this.items.splice(insertIndex, 0, item);
    return this;
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Priority queue is empty');
    }
    return this.items.shift().element;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[0].element;
  }

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

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

  clear() {
    this.items = [];
    return this;
  }

  toArray() {
    return this.items.map((item) => item.element);
  }
}

// Usage examples
const queue = new Queue();
queue.enqueue('first').enqueue('second').enqueue('third');

console.log(queue.dequeue()); // 'first'
console.log(queue.peek()); // 'second'

const pqueue = new PriorityQueue();
pqueue.enqueue('low priority task', 3);
pqueue.enqueue('high priority task', 1);
pqueue.enqueue('medium priority task', 2);

console.log(pqueue.dequeue()); // 'high priority task'
console.log(pqueue.dequeue()); // 'medium priority task'

Linked List

class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Add element to end
  append(data) {
    const newNode = new ListNode(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this;
  }

  // Add element to beginning
  prepend(data) {
    const newNode = new ListNode(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;
    return this;
  }

  // Insert at specific index
  insertAt(index, data) {
    if (index < 0 || index > this.length) {
      throw new Error('Index out of bounds');
    }

    if (index === 0) {
      return this.prepend(data);
    }

    if (index === this.length) {
      return this.append(data);
    }

    const newNode = new ListNode(data);
    let current = this.head;

    for (let i = 0; i < index - 1; i++) {
      current = current.next;
    }

    newNode.next = current.next;
    current.next = newNode;
    this.length++;

    return this;
  }

  // Remove from beginning
  removeFirst() {
    if (!this.head) {
      return null;
    }

    const data = this.head.data;
    this.head = this.head.next;

    if (!this.head) {
      this.tail = null;
    }

    this.length--;
    return data;
  }

  // Remove from end
  removeLast() {
    if (!this.head) {
      return null;
    }

    if (this.head === this.tail) {
      const data = this.head.data;
      this.head = null;
      this.tail = null;
      this.length--;
      return data;
    }

    let current = this.head;
    while (current.next !== this.tail) {
      current = current.next;
    }

    const data = this.tail.data;
    current.next = null;
    this.tail = current;
    this.length--;

    return data;
  }

  // Remove at specific index
  removeAt(index) {
    if (index < 0 || index >= this.length) {
      throw new Error('Index out of bounds');
    }

    if (index === 0) {
      return this.removeFirst();
    }

    let current = this.head;
    for (let i = 0; i < index - 1; i++) {
      current = current.next;
    }

    const data = current.next.data;
    current.next = current.next.next;

    if (!current.next) {
      this.tail = current;
    }

    this.length--;
    return data;
  }

  // Find element
  find(predicate) {
    let current = this.head;
    let index = 0;

    while (current) {
      if (predicate(current.data, index)) {
        return { data: current.data, index };
      }
      current = current.next;
      index++;
    }

    return null;
  }

  // Get element at index
  get(index) {
    if (index < 0 || index >= this.length) {
      throw new Error('Index out of bounds');
    }

    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }

    return current.data;
  }

  // Check if list contains element
  contains(data) {
    return this.find((item) => item === data) !== null;
  }

  // Get size
  size() {
    return this.length;
  }

  // Check if empty
  isEmpty() {
    return this.length === 0;
  }

  // Clear list
  clear() {
    this.head = null;
    this.tail = null;
    this.length = 0;
    return this;
  }

  // Convert to array
  toArray() {
    const result = [];
    let current = this.head;

    while (current) {
      result.push(current.data);
      current = current.next;
    }

    return result;
  }

  // Iterator support
  *[Symbol.iterator]() {
    let current = this.head;
    while (current) {
      yield current.data;
      current = current.next;
    }
  }

  // String representation
  toString() {
    return this.toArray().join(' -> ');
  }
}

// Usage examples
const list = new LinkedList();
list.append(1).append(2).append(3);
list.prepend(0);
list.insertAt(2, 1.5);

console.log(list.toString()); // "0 -> 1 -> 1.5 -> 2 -> 3"
console.log(list.find((x) => x > 2)); // { data: 3, index: 4 }

for (const item of list) {
  console.log(item);
}

Binary Tree

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

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

  // Insert element (for BST)
  insert(data) {
    this.root = this._insertNode(this.root, data);
    return this;
  }

  _insertNode(node, data) {
    if (node === null) {
      return new TreeNode(data);
    }

    if (data < node.data) {
      node.left = this._insertNode(node.left, data);
    } else if (data > node.data) {
      node.right = this._insertNode(node.right, data);
    }

    return node;
  }

  // Search for element
  search(data) {
    return this._searchNode(this.root, data);
  }

  _searchNode(node, data) {
    if (node === null || node.data === data) {
      return node;
    }

    if (data < node.data) {
      return this._searchNode(node.left, data);
    } else {
      return this._searchNode(node.right, data);
    }
  }

  // Remove element
  remove(data) {
    this.root = this._removeNode(this.root, data);
    return this;
  }

  _removeNode(node, data) {
    if (node === null) {
      return null;
    }

    if (data < node.data) {
      node.left = this._removeNode(node.left, data);
    } else if (data > node.data) {
      node.right = this._removeNode(node.right, data);
    } else {
      // Node to be deleted found
      if (node.left === null) {
        return node.right;
      } else if (node.right === null) {
        return node.left;
      } else {
        // Node with two children
        const minValue = this._findMin(node.right);
        node.data = minValue;
        node.right = this._removeNode(node.right, minValue);
      }
    }

    return node;
  }

  _findMin(node) {
    while (node.left !== null) {
      node = node.left;
    }
    return node.data;
  }

  // Tree traversals
  inorderTraversal() {
    const result = [];
    this._inorder(this.root, result);
    return result;
  }

  _inorder(node, result) {
    if (node !== null) {
      this._inorder(node.left, result);
      result.push(node.data);
      this._inorder(node.right, result);
    }
  }

  preorderTraversal() {
    const result = [];
    this._preorder(this.root, result);
    return result;
  }

  _preorder(node, result) {
    if (node !== null) {
      result.push(node.data);
      this._preorder(node.left, result);
      this._preorder(node.right, result);
    }
  }

  postorderTraversal() {
    const result = [];
    this._postorder(this.root, result);
    return result;
  }

  _postorder(node, result) {
    if (node !== null) {
      this._postorder(node.left, result);
      this._postorder(node.right, result);
      result.push(node.data);
    }
  }

  // Level order traversal (BFS)
  levelOrderTraversal() {
    if (!this.root) return [];

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

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

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

    return result;
  }

  // Tree properties
  height() {
    return this._getHeight(this.root);
  }

  _getHeight(node) {
    if (node === null) return -1;

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

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

  size() {
    return this._getSize(this.root);
  }

  _getSize(node) {
    if (node === null) return 0;
    return 1 + this._getSize(node.left) + this._getSize(node.right);
  }

  isEmpty() {
    return this.root === null;
  }

  // Validation
  isValidBST() {
    return this._isValidBST(this.root, null, null);
  }

  _isValidBST(node, min, max) {
    if (node === null) return true;

    if (
      (min !== null && node.data <= min) ||
      (max !== null && node.data >= max)
    ) {
      return false;
    }

    return (
      this._isValidBST(node.left, min, node.data) &&
      this._isValidBST(node.right, node.data, max)
    );
  }
}

// Usage examples
const bst = new BinaryTree();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach((val) => bst.insert(val));

console.log(bst.inorderTraversal()); // [1, 3, 4, 6, 7, 8, 10, 13, 14]
console.log(bst.preorderTraversal()); // [8, 3, 1, 6, 4, 7, 10, 14, 13]
console.log(bst.levelOrderTraversal()); // [8, 3, 10, 1, 6, 14, 4, 7, 13]

console.log(bst.search(6)); // TreeNode with data 6
console.log(bst.height()); // 3
console.log(bst.isValidBST()); // true

bst.remove(3);
console.log(bst.inorderTraversal()); // [1, 4, 6, 7, 8, 10, 13, 14]

Conclusion

Understanding data structures is fundamental to writing efficient JavaScript code. Built-in structures like arrays, objects, Maps, and Sets provide powerful tools for most use cases, while custom implementations of stacks, queues, linked lists, and trees give you complete control over data organization and algorithms. Choose the right data structure based on your specific use case, considering factors like insertion/deletion frequency, search requirements, and memory constraints.

JavaScript Data Structures: Arrays, Objects, Maps, Sets, and More