Foundations Patterns Graphs / DP Interview

medium

30 minIntern through senior

When to use. Hierarchical data, hierarchical decisions, or a graph you know is acyclic and rooted.

Complexity. Time Typical DFS/BFS O(n); BST ops O(h). Space O(h) recursion or O(n) for queues/maps.

Who gets asked. Tree DFS is intern-core. LCA, serialize, and BST-from-preorder show up through senior.

Prereq. Recursion and queues.

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. Tree DFS is intern-core. Lowest common ancestor, serialize/deserialize, and BST-from-preorder show up through senior. Priority queues are a different pattern — see Heaps.

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

Longest root-to-leaf path counted in nodes. Empty tree is 0. DFS, O(n) time, O(h) stack.

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.

Saved in this browser. No account.

PreviousBacktracking