A tree is data shaped like a family tree: one node at the top, the root, and each node may have children, which may have children of their own. A node with no children is a leaf. The DOM is a tree: the document sits at the root, <html> is its child element, and every element's children are the nodes directly inside it. Traversing a tree means visiting every node once, for example to collect the ones that pass a test or to count them.
There are two main orders. Depth-first goes as deep as it can down one branch, all the way to its leaves, before it moves on to the next sibling. Breadth-first goes level by level: the root, then all of its children, then all of their children. In a family tree, depth-first follows one family line down to the youngest generation before turning to the next sibling's line; breadth-first meets everyone generation by generation.
Here's a small part of a page, drawn as a tree, with each element's depth, its distance from <main>:
// <main><article><h2>Title</h2><p>Text</p></article><aside><ul><li>Link</li></ul></aside></main>
//
// main depth 0
// ├─ article depth 1
// │ ├─ h2 depth 2
// │ └─ p depth 2
// └─ aside depth 1
// └─ ul depth 2
// └─ li depth 3
| Step | Depth-first visits | Breadth-first visits |
|---|---|---|
| 1 | main | main |
| 2 | article | article |
| 3 | h2 | aside |
| 4 | p | h2 |
| 5 | aside | p |
| 6 | ul | ul |
| 7 | li | li |
Both visit all seven elements; only the order differs. Depth-first finishes article and everything in it before it touches aside. Breadth-first sees both elements at depth 1 before anything at depth 2, so it reaches the nodes nearest the root first.
Depth-first comes in two common variants. Pre-order visits a node before its children, as in the table: that's the order of the start tags in the HTML, which the DOM calls document order. Post-order visits a node after its children: h2, p, article, li, ul, aside, main, the order of the end tags. You meet traversal wherever data nests: the DOM, nested comments and menus, folders and files, and the syntax trees that tools such as Babel and ESLint walk through.
Document order is the order of the nodes in the DOM (Document Object Model), the tree of objects the browser builds from a page's HTML. In a page fresh from its HTML, it's the order you meet things reading the source from top to bottom: a node comes first, then everything inside it, in the same order, then its next sibling. Elements aren't the only nodes: the text between tags and comments are nodes too, and each has its place.
It's like a book's table of contents: a chapter, then all of its sections, and only then the next chapter.
Here are the nodes of <section><h2>Menu</h2><ul><li>Tea</li><li>Cake<!-- new --></li></ul><p>Open daily</p></section>, numbered in document order:
| Position | Node | Its parent |
|---|---|---|
| 1 | <section> | None inside this snippet |
| 2 | <h2> | <section> |
| 3 | The text Menu | <h2> |
| 4 | <ul> | <section> |
| 5 | The first <li> | <ul> |
| 6 | The text Tea | The first <li> |
| 7 | The second <li> | <ul> |
| 8 | The text Cake | The second <li> |
| 9 | The comment <!-- new --> | The second <li> |
| 10 | <p> | <section> |
| 11 | The text Open daily | <p> |
Look at <ul> and <p>: they're siblings, at positions 4 and 10, and everything inside <ul> comes between them. Going all the way down before moving on to the next sibling makes this a depth-first order. In HTML with line breaks and indentation, the whitespace between tags becomes text nodes too, and they take positions as well.
[...document.querySelectorAll("section *")].map((el) => el.tagName);
// ["H2", "UL", "LI", "LI", "P"]: positions 2, 4, 5, 7, and 10, with no text or comments
The order is defined on the tree, not on the file, so after a script moves a node, document order follows where the node is now. The DOM uses it throughout: querySelectorAll and getElementsByClassName return elements in document order, a TreeWalker steps through nodes in it, and a.compareDocumentPosition(b) tells you which of two nodes comes first. The default Tab order, and the order screen readers read a page in, follow it too.
Write getElementsByClassName(root, classNames), a version of the built-in method that walks the tree itself. classNames is a string of one or more class names separated by spaces. Return an array of every element inside root (not root itself) whose class list has all of them, in document order.
Match whole class names, case-sensitively: item matches class="item active" but not class="item-active" or class="Item". Extra spaces don't matter, and a string with no class names gives []. root can be an element or document.
Walk the tree with children (or firstElementChild and nextElementSibling). Don't call querySelector, querySelectorAll, getElementsByClassName, getElementsByTagName, or matches.
// <ul id="menu"><li class="item active">One</li><li class="item">Two</li></ul>
getElementsByClassName(document.getElementById("menu"), "item"); // [li, li]
getElementsByClassName(document.getElementById("menu"), "active item"); // [the first li]
getElementsByClassName(document, ""); // []
const ids = (elements) => elements.map((element) => element.id);
const root = document.getElementById("root");
expect(ids(getElementsByClassName(root, "item"))).toEqual(["one", "three", "five", "six"]);
const result = getElementsByClassName(document.getElementById("root"), "item");
expect(Array.isArray(result)).toBe(true);
const ids = (elements) => elements.map((element) => element.id);
expect(ids(getElementsByClassName(document.getElementById("root"), "item"))).not.toContain("root");
expect(ids(getElementsByClassName(document, "item"))).toEqual(["root", "one", "three", "five", "six", "outside"]);
const ids = (elements) => elements.map((element) => element.id);
expect(ids(getElementsByClassName(document.getElementById("root"), "active"))).toEqual(["one", "three"]);
const ids = (elements) => elements.map((element) => element.id);
const root = document.getElementById("root");
expect(ids(getElementsByClassName(root, "active item"))).toEqual(["one", "three"]);
expect(ids(getElementsByClassName(root, "extra item"))).toEqual(["three"]);
expect(ids(getElementsByClassName(root, "item missing"))).toEqual([]);
const ids = (elements) => elements.map((element) => element.id);
const root = document.getElementById("root");
expect(ids(getElementsByClassName(root, " active item "))).toEqual(["one", "three"]);
expect(getElementsByClassName(root, "")).toEqual([]);
expect(getElementsByClassName(root, " ")).toEqual([]);
const ids = (elements) => elements.map((element) => element.id);
expect(ids(getElementsByClassName(document.getElementById("root"), "Item"))).toEqual(["four"]);
const ids = (elements) => elements.map((element) => element.id);
const root = document.getElementById("root");
const banned = [Element.prototype, Document.prototype].flatMap((proto) =>
["querySelector", "querySelectorAll", "getElementsByClassName", "getElementsByTagName", "matches"]
.filter((name) => name in proto)
.map((name) => ({ proto, name, original: proto[name] })),
);
for (const { proto, name } of banned) {
proto[name] = () => {
throw new Error("Don't call " + name + ": walk the tree yourself with children");
};
}
let found;
try {
found = getElementsByClassName(root, "item");
} finally {
for (const { proto, name, original } of banned) proto[name] = original;
}
expect(ids(found)).toEqual(["one", "three", "five", "six"]);
Run tests runs every test on your code, here in your browser. The problem is solved when they all pass.
Ctrl + Enter runs the tests (⌘ + Enter on a Mac).
I'm here to help with getElementsByClassName by walking the tree. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.