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.
The page has a tree of checkboxes. Each item is an <li> whose <label> holds its checkbox, and an item with children has a nested <ul> of more items after its label:
<ul id="permissions">
<li>
<label><input type="checkbox" id="docs"> Documents</label>
<ul>
<li><label><input type="checkbox" id="view"> View</label></li>
<li><label><input type="checkbox" id="edit"> Edit</label></li>
<li>
<label><input type="checkbox" id="share"> Share</label>
<ul>
<li><label><input type="checkbox" id="team"> With your team</label></li>
<li><label><input type="checkbox" id="public"> With anyone</label></li>
</ul>
</li>
</ul>
</li>
<li><label><input type="checkbox" id="billing"> Billing</label></li>
</ul>
Write setupCheckboxTree(root), where root is the outer <ul>. When the user checks or unchecks a box, every box below it takes the same state. Clicking an indeterminate box checks it: the browser clears its indeterminate and sets checked.
Then every box above it updates from its direct children: checked when they're all checked, unchecked when none is checked or indeterminate, and indeterminate otherwise. An indeterminate box has indeterminate set to true and checked set to false; checked and unchecked boxes have indeterminate set to false.
On setup, work out every parent box from the boxes below it by the same rule, so a tree that starts with some boxes checked shows the right parents.
Show the mixed state with the indeterminate property only, and don't add aria-checked. Browsers already report an indeterminate native checkbox to screen readers as mixed, and ARIA in HTML doesn't allow aria-checked on one.
setupCheckboxTree(document.getElementById("permissions"));
// check "With your team": Share and Documents become indeterminate
// check "With anyone": Share is checked; Documents stays indeterminate
// click Documents: it's checked, and so is everything below it
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
const all = ["docs", "view", "edit", "share", "team", "public", "billing"];
setupCheckboxTree(document.getElementById("permissions"));
fire(box("docs"), "click");
expect(all.map(state)).toEqual(["checked", "checked", "checked", "checked", "checked", "checked", "unchecked"]);
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
const all = ["docs", "view", "edit", "share", "team", "public", "billing"];
setupCheckboxTree(document.getElementById("permissions"));
fire(box("docs"), "click");
fire(box("docs"), "click");
expect(all.map(state)).toEqual(["unchecked", "unchecked", "unchecked", "unchecked", "unchecked", "unchecked", "unchecked"]);
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
setupCheckboxTree(document.getElementById("permissions"));
fire(box("view"), "click");
expect(state("docs")).toBe("indeterminate");
fire(box("edit"), "click");
fire(box("share"), "click");
expect(state("docs")).toBe("checked");
fire(box("edit"), "click");
expect(state("docs")).toBe("indeterminate");
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
setupCheckboxTree(document.getElementById("permissions"));
fire(box("team"), "click");
expect(state("share")).toBe("indeterminate");
expect(state("docs")).toBe("indeterminate");
fire(box("public"), "click");
expect(state("share")).toBe("checked");
expect(state("docs")).toBe("indeterminate");
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
setupCheckboxTree(document.getElementById("permissions"));
fire(box("team"), "click");
fire(box("team"), "click");
expect(state("share")).toBe("unchecked");
expect(state("docs")).toBe("unchecked");
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
const below = ["view", "edit", "share", "team", "public"];
setupCheckboxTree(document.getElementById("permissions"));
fire(box("team"), "click");
fire(box("docs"), "click");
expect(state("docs")).toBe("checked");
expect(below.map(state)).toEqual(["checked", "checked", "checked", "checked", "checked"]);
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
const all = ["docs", "view", "edit", "share", "team", "public", "billing"];
for (const id of ["view", "edit", "team", "public"]) box(id).checked = true;
setupCheckboxTree(document.getElementById("permissions"));
expect(all.map(state)).toEqual(["checked", "checked", "checked", "checked", "checked", "checked", "unchecked"]);
const box = (id) => document.getElementById(id);
const state = (id) => (box(id).indeterminate ? (box(id).checked ? "checked and indeterminate" : "indeterminate") : box(id).checked ? "checked" : "unchecked");
const all = ["docs", "view", "edit", "share", "team", "public", "billing"];
for (const id of ["docs", "share", "view"]) box(id).checked = true;
setupCheckboxTree(document.getElementById("permissions"));
expect(all.map(state)).toEqual(["indeterminate", "checked", "unchecked", "unchecked", "unchecked", "unchecked", "unchecked"]);
const root = document.getElementById("permissions");
setupCheckboxTree(root);
fire(document.getElementById("team"), "click");
fire(document.getElementById("view"), "click");
expect(root.querySelectorAll("[aria-checked]")).toHaveLength(0);
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 Checkbox tree with indeterminate parents. 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.