Trees

A Tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear structures, trees branch out from a single root node.

Tree Terminology

Binary Tree

A Binary Tree is a tree where each node has at most 2 children (left and right).

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

Binary Search Tree (BST)

A BST is a binary tree with a special property:

• Left subtree contains values less than the parent
• Right subtree contains values greater than the parent

This property enables O(log n) search!

BST Implementation

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

  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }
}

// Usage
const bst = new BST();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
console.log(bst.search(40)); // true
console.log(bst.search(45)); // false

Tree Traversals

1. In-Order (Left, Root, Right)

Visits nodes in sorted order for BST.

function inOrder(node) {
  if (!node) return;
  inOrder(node.left);
  console.log(node.value);
  inOrder(node.right);
}
// Output: 20, 30, 40, 50, 60, 70, 80

2. Pre-Order (Root, Left, Right)

Used to copy a tree or get prefix expression.

function preOrder(node) {
  if (!node) return;
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
}
// Output: 50, 30, 20, 40, 70, 60, 80

3. Post-Order (Left, Right, Root)

Used to delete a tree or get postfix expression.

function postOrder(node) {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
}
// Output: 20, 40, 30, 60, 80, 70, 50

4. Level-Order (BFS)

Visits nodes level by level using a queue.

function levelOrder(root) {
  if (!root) return;
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}
// Output: 50, 30, 70, 20, 40, 60, 80

BST Operations Complexity

Types of Trees

Real-World Applications

• File Systems — Directory structure
• DOM — HTML document tree
• Databases — B-trees for indexing
• Autocomplete — Trie data structure
• Decision Making — Decision trees in ML

What's Next?

Next, we'll explore Graphs — the most general data structure that can represent any relationship between objects, essential for social networks, maps, and many algorithms.