Trees

Trees are hierarchical data structures with a root node and child nodes. Binary trees have at most two children per node.

Animated Visualization

Step 1 of 4

Binary Search Tree: Root = 10, Left < 10, Right > 10

javascript

← Scroll →

// Binary Tree Node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
// Binary Search Tree
class BST {
  constructor() {
    this.root = null;
  }
  // Insert a value
  insert(value) {
    this.root = this.insertNode(this.root, value);
  }
  insertNode(node, value) {
    if (!node) {
      return new TreeNode(value);
    }
    if (value < node.value) {
      node.left = this.insertNode(node.left, value);
    } else {
      node.right = this.insertNode(node.right, value);
    }
    return node;
  }
  // Search for a value
  search(value) {
    return this.searchNode(this.root, value);
  }
  searchNode(node, value) {
    if (!node || node.value === value) {
      return node;
    }
    if (value < node.value) {
      return this.searchNode(node.left, value);
    }
    return this.searchNode(node.right, value);
  }
  // Inorder Traversal (Left, Root, Right)
  inorder(node = this.root) {
    if (node) {
      this.inorder(node.left);
      console.log(node.value);
      this.inorder(node.right);
    }
  }
  // Time Complexity:
  // Insert: O(log n) average, O(n) worst
  // Search: O(log n) average, O(n) worst
  // Traversal: O(n)

Swipe horizontally to view full code

Explanation

Trees are hierarchical data structures. Binary Search Trees maintain order: left subtree < root < right subtree. This enables efficient search, insert, and delete operations with O(log n) average time complexity.

Operations & Complexity

InsertO(log n)

Insert in sorted order

SearchO(log n)

Binary search through tree

DeleteO(log n)

Remove node maintaining order

TraversalO(n)

Visit all nodes

Time Complexity