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

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 ', 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