Trees: Hierarchical Data

Learn about trees, the non-linear data structures that are fundamental to file systems, databases, and especially the **Document Object Model (DOM)** that structures every web page.

What Is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike arrays or linked lists, which are linear, trees are non-linear. The topmost node is called the **root**. Each node can have zero or more child nodes. A node with no children is a **leaf**.

Think of a family tree or a company's organizational chart. In frontend development, the most important tree is the DOM, where the <html> tag is the root and every other element is a node. This structure is what allows JavaScript to efficiently find and manipulate page elements.

Binary Search Trees (BSTs)

A **Binary Search Tree** is a special type of tree with important properties that make searching for data incredibly efficient:

Each node has at most two children (a left child and a right child).
For any given node, all values in its **left subtree** are less than the node's value.
For any given node, all values in its **right subtree** are greater than the node's value.

This ordering means we can find any value in the tree with an average time complexity of **O(log n)**, which is significantly faster than the O(n) required to search an unsorted array.

Interactive Binary Search Tree

Insert, search for, and delete nodes to see how a BST works.

OPERATION LOG

Tree Traversal Visualizer

See how different algorithms visit nodes in a tree.

Traversal Path

Real-World Use Cases

Trees are everywhere in computer science. Click on an example to learn more.

File Systems

Your computer's folder structure is a tree.

Database Indexing

Databases use B-Trees to quickly search for data.

HTML DOM

Browsers parse HTML into a Document Object Model (DOM) tree.

Autocomplete

Tries, a special kind of tree, are used for autocomplete suggestions.

Interview Problems

Practice with classic tree-based interview questions.

The Common Pitfall

A common mistake is to only check if node.left.value < node.value and node.right.value > node.value. This fails for the tree below because while 6 is greater than its parent 15's left child, it is NOT greater than the root node 10, violating the BST property.

Click "Next Step" to begin validation.

Solution Code (JavaScript)

function isValidBST(root) {
  // Helper function with min/max boundaries
  function validate(node, min, max) {
    // An empty tree is a valid BST
    if (!node) {
      return true;
    }

    // The current node's value must be within the valid range
    if (
      (min !== null && node.value <= min) ||
      (max !== null && node.value >= max)
    ) {
      return false;
    }

    // Recursively check the left and right subtrees
    // Left subtree: update the 'max' boundary
    // Right subtree: update the 'min' boundary
    return (
      validate(node.left, min, node.value) &&
      validate(node.right, node.value, max)
    );
  }

  return validate(root, null, null);
}

Coding Challenge

Select a Problem

Given the `root` of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Go Deeper with "Cracking the Coding Interview"

To master tree algorithms and tackle common interview questions, "Cracking the Coding Interview" by Gayle Laakmann McDowell is an indispensable resource.

Previous

Hash Tables

Next

Graphs

J

Dafin Edison J

Creator & Developer of Jaconir

I build things for the web. From immersive games to practical tools, my goal is to create products that people love to use and to share the knowledge I've gained along the way.