0
# Tree Traversal
1

2
Comprehensive tree traversal algorithms and node navigation utilities for exploring the Lexical node tree structure. These functions provide efficient methods for walking through the editor's document tree, finding specific nodes, and performing complex tree operations.
3

4
## Capabilities
5

6
### Depth-First Search (DFS)
7

8
Performs depth-first tree traversal starting from a specified node, returning all nodes with their depth information.
9

10
```typescript { .api }
11
/**
12
 * "Depth-First Search" starts at the root/top node of a tree and goes as far as it can down a branch end
13
 * before backtracking and finding a new path. Consider solving a maze by hugging either wall, moving down a
14
 * branch until you hit a dead-end (leaf) and backtracking to find the nearest branching path and repeat.
15
 * It will then return all the nodes found in the search in an array of objects.
16
 * @param startNode - The node to start the search, if omitted, it will start at the root node.
17
 * @param endNode - The node to end the search, if omitted, it will find all descendants of the startingNode.
18
 * @returns An array of objects of all the nodes found by the search, including their depth into the tree.
19
 * {depth: number, node: LexicalNode} It will always return at least 1 node (the start node).
20
 */
21
function $dfs(
22
  startNode?: LexicalNode,
23
  endNode?: LexicalNode
24
): Array<DFSNode>;
25

26
interface DFSNode {
27
  readonly depth: number;
28
  readonly node: LexicalNode;
29
}
30
```
31

32
**Usage Examples:**
33

34
```typescript
35
import { $dfs } from "@lexical/utils";
36
import { $getRoot } from "lexical";
37

38
// Traverse entire document tree
39
const allNodes = $dfs();
40
allNodes.forEach(({ node, depth }) => {
41
  const indent = '  '.repeat(depth);
42
  console.log(`${indent}${node.getType()}`);
43
});
44

45
// Traverse from specific node
46
const paragraphNode = $getNodeByKey('paragraph-key');
47
const paragraphDescendants = $dfs(paragraphNode);
48

49
// Traverse between specific nodes
50
const startNode = $getNodeByKey('start-key');
51
const endNode = $getNodeByKey('end-key');
52
const nodesBetween = $dfs(startNode, endNode);
53

54
// Find all text nodes in document
55
const textNodes = $dfs()
56
  .filter(({ node }) => node.getType() === 'text')
57
  .map(({ node }) => node);
58
```
59

60
### DFS Iterator
61

62
Memory-efficient iterator for depth-first search that computes nodes on-demand with O(1) memory usage.
63

64
```typescript { .api }
65
/**
66
 * $dfs iterator (left to right). Tree traversal is done on the fly as new values are requested with O(1) memory.
67
 * @param startNode - The node to start the search, if omitted, it will start at the root node.
68
 * @param endNode - The node to end the search, if omitted, it will find all descendants of the startingNode.
69
 * @returns An iterator, each yielded value is a DFSNode. It will always return at least 1 node (the start node).
70
 */
71
function $dfsIterator(
72
  startNode?: LexicalNode,
73
  endNode?: LexicalNode
74
): IterableIterator<DFSNode>;
75
```
76

77
**Usage Examples:**
78

79
```typescript
80
import { $dfsIterator } from "@lexical/utils";
81

82
// Memory-efficient traversal for large documents
83
for (const { node, depth } of $dfsIterator()) {
84
  if (node.getType() === 'heading') {
85
    console.log(`Found heading at depth ${depth}:`, node.getTextContent());
86
    break; // Can exit early without computing remaining nodes
87
  }
88
}
89

90
// Process nodes in chunks
91
const iterator = $dfsIterator();
92
const batch: DFSNode[] = [];
93
for (const dfsNode of iterator) {
94
  batch.push(dfsNode);
95
  if (batch.length === 10) {
96
    // Process batch of 10 nodes
97
    processBatch(batch);
98
    batch.length = 0;
99
  }
100
}
101
```
102

103
### Reverse DFS
104

105
Performs right-to-left depth-first search traversal.
106

107
```typescript { .api }
108
/**
109
 * Performs a right-to-left preorder tree traversal.
110
 * From the starting node it goes to the rightmost child, than backtracks to parent and finds new rightmost path.
111
 * @param startNode - The node to start the search, if omitted, it will start at the root node.
112
 * @param endNode - The node to end the search, if omitted, it will find all descendants of the startingNode.
113
 * @returns An array of DFSNode objects in reverse traversal order.
114
 */
115
function $reverseDfs(
116
  startNode?: LexicalNode,
117
  endNode?: LexicalNode
118
): Array<DFSNode>;
119

120
function $reverseDfsIterator(
121
  startNode?: LexicalNode,
122
  endNode?: LexicalNode
123
): IterableIterator<DFSNode>;
124
```
125

126
### Node Navigation Functions
127

128
#### Get Adjacent Caret
129

130
Gets the adjacent caret in the same direction.
131

132
```typescript { .api }
133
/**
134
 * Get the adjacent caret in the same direction
135
 * @param caret - A caret or null
136
 * @returns caret.getAdjacentCaret() or null
137
 */
138
function $getAdjacentCaret<D extends CaretDirection>(
139
  caret: null | NodeCaret<D>
140
): null | SiblingCaret<LexicalNode, D>;
141
```
142

143
#### Get Node Depth
144

145
Calculates the depth of a node in the tree hierarchy.
146

147
```typescript { .api }
148
/**
149
 * Calculates depth of a node in the tree
150
 * @param node - The node to calculate depth for
151
 * @returns The depth level (0 for root)
152
 */
153
function $getDepth(node: null | LexicalNode): number;
154
```
155

156
**Usage Examples:**
157

158
```typescript
159
import { $getDepth } from "@lexical/utils";
160

161
const someNode = $getNodeByKey('node-key');
162
const depth = $getDepth(someNode);
163

164
// Use depth for indentation or styling
165
if (depth > 3) {
166
  // Apply deep nesting styles
167
  addClassNamesToElement(element, 'deeply-nested');
168
}
169
```
170

171
#### Get Next Sibling or Parent Sibling
172

173
Finds the next sibling node or the closest parent sibling with depth information.
174

175
```typescript { .api }
176
/**
177
 * Returns the Node sibling when this exists, otherwise the closest parent sibling. For example
178
 * R -> P -> T1, T2
179
 *   -> P2
180
 * returns T2 for node T1, P2 for node T2, and null for node P2.
181
 * @param node - LexicalNode.
182
 * @returns An array (tuple) containing the found Lexical node and the depth difference, or null, if this node doesn't exist.
183
 */
184
function $getNextSiblingOrParentSibling(
185
  node: LexicalNode
186
): null | [LexicalNode, number];
187
```
188

189
#### Get Next Right Preorder Node
190

191
Gets the next node in right-to-left preorder traversal.
192

193
```typescript { .api }
194
/**
195
 * Performs a right-to-left preorder tree traversal.
196
 * From the starting node it goes to the rightmost child, than backtracks to parent and finds new rightmost path.
197
 * It will return the next node in traversal sequence after the startingNode.
198
 * The traversal is similar to $dfs functions above, but the nodes are visited right-to-left, not left-to-right.
199
 * @param startingNode - The node to start the search.
200
 * @returns The next node in pre-order right to left traversal sequence or null, if the node does not exist
201
 */
202
function $getNextRightPreorderNode(
203
  startingNode: LexicalNode
204
): LexicalNode | null;
205
```
206

207
### Node Search Functions
208

209
#### Find Nearest Node of Type
210

211
Searches up the tree to find the nearest ancestor of a specific type.
212

213
```typescript { .api }
214
/**
215
 * Takes a node and traverses up its ancestors (toward the root node)
216
 * in order to find a specific type of node.
217
 * @param node - the node to begin searching.
218
 * @param klass - an instance of the type of node to look for.
219
 * @returns the node of type klass that was passed, or null if none exist.
220
 */
221
function $getNearestNodeOfType<T extends ElementNode>(
222
  node: LexicalNode,
223
  klass: Klass<T>
224
): T | null;
225
```
226

227
**Usage Examples:**
228

229
```typescript
230
import { $getNearestNodeOfType } from "@lexical/utils";
231
import { ListNode, ListItemNode } from "@lexical/list";
232

233
const currentNode = $getSelection()?.getNodes()[0];
234
if (currentNode) {
235
  // Find containing list
236
  const listNode = $getNearestNodeOfType(currentNode, ListNode);
237
  if (listNode) {
238
    console.log('Inside a list:', listNode.getListType());
239
  }
240
  
241
  // Find containing list item
242
  const listItemNode = $getNearestNodeOfType(currentNode, ListItemNode);
243
  if (listItemNode) {
244
    console.log('Inside list item:', listItemNode.getValue());
245
  }
246
}
247
```
248

249
#### Find Nearest Block Element Ancestor
250

251
Returns the nearest block element ancestor or throws an error if none exists.
252

253
```typescript { .api }
254
/**
255
 * Returns the element node of the nearest ancestor, otherwise throws an error.
256
 * @param startNode - The starting node of the search
257
 * @returns The ancestor node found
258
 */
259
function $getNearestBlockElementAncestorOrThrow(
260
  startNode: LexicalNode
261
): ElementNode;
262
```
263

264
#### Find Matching Parent
265

266
Searches up the tree for a parent node that matches a test function.
267

268
```typescript { .api }
269
/**
270
 * Starts with a node and moves up the tree (toward the root node) to find a matching node based on
271
 * the search parameters of the findFn. (Consider JavaScripts' .find() function where a testing function must be
272
 * passed as an argument. eg. if( (node) => node.__type === 'div') ) return true; otherwise return false
273
 * @param startingNode - The node where the search starts.
274
 * @param findFn - A testing function that returns true if the current node satisfies the testing parameters.
275
 * @returns A parent node that matches the findFn parameters, or null if one wasn't found.
276
 */
277
function $findMatchingParent<T extends LexicalNode>(
278
  startingNode: LexicalNode,
279
  findFn: (node: LexicalNode) => node is T
280
): T | null;
281
function $findMatchingParent(
282
  startingNode: LexicalNode,
283
  findFn: (node: LexicalNode) => boolean
284
): LexicalNode | null;
285
```
286

287
**Usage Examples:**
288

289
```typescript
290
import { $findMatchingParent } from "@lexical/utils";
291

292
const currentNode = $getSelection()?.getNodes()[0];
293
if (currentNode) {
294
  // Find nearest editable element
295
  const editableParent = $findMatchingParent(
296
    currentNode,
297
    (node) => $isElementNode(node) && node.isEditable()
298
  );
299
  
300
  // Find nearest node with specific attribute
301
  const styledParent = $findMatchingParent(
302
    currentNode,
303
    (node) => node.hasFormat('bold')
304
  );
305
  
306
  // Type-safe search with type predicate
307
  const tableParent = $findMatchingParent(
308
    currentNode,
309
    (node): node is TableNode => node instanceof TableNode
310
  );
311
}
312
```
313

314
### Child Iterator Functions
315

316
Safe iteration over element children that preserves sibling references during mutation.
317

318
```typescript { .api }
319
/**
320
 * Return an iterator that yields each child of node from first to last, taking
321
 * care to preserve the next sibling before yielding the value in case the caller
322
 * removes the yielded node.
323
 * @param node - The node whose children to iterate
324
 * @returns An iterator of the node's children
325
 */
326
function $firstToLastIterator(node: ElementNode): Iterable<LexicalNode>;
327

328
/**
329
 * Return an iterator that yields each child of node from last to first, taking
330
 * care to preserve the previous sibling before yielding the value in case the caller
331
 * removes the yielded node.
332
 * @param node - The node whose children to iterate
333
 * @returns An iterator of the node's children
334
 */
335
function $lastToFirstIterator(node: ElementNode): Iterable<LexicalNode>;
336
```
337

338
**Usage Examples:**
339

340
```typescript
341
import { $firstToLastIterator, $lastToFirstIterator } from "@lexical/utils";
342

343
const parentElement = $getNodeByKey('parent-key') as ElementNode;
344

345
// Safe forward iteration (allows removal during iteration)
346
for (const child of $firstToLastIterator(parentElement)) {
347
  if (child.getType() === 'text' && child.getTextContent().trim() === '') {
348
    child.remove(); // Safe to remove during iteration
349
  }
350
}
351

352
// Safe backward iteration
353
for (const child of $lastToFirstIterator(parentElement)) {
354
  if (shouldProcessChild(child)) {
355
    processChild(child);
356
  }
357
}
358
```
359

360
### Filter Function
361

362
Filters an array of nodes using a transform function.
363

364
```typescript { .api }
365
/**
366
 * Filter the nodes
367
 * @param nodes - Array of nodes that needs to be filtered
368
 * @param filterFn - A filter function that returns node if the current node satisfies the condition otherwise null
369
 * @returns Array of filtered nodes
370
 */
371
function $filter<T>(
372
  nodes: Array<LexicalNode>,
373
  filterFn: (node: LexicalNode) => null | T
374
): Array<T>;
375
```
376

377
**Usage Examples:**
378

379
```typescript
380
import { $filter, $dfs } from "@lexical/utils";
381
import { $isTextNode } from "lexical";
382

383
// Get all text nodes from traversal
384
const allNodes = $dfs();
385
const textNodes = $filter(allNodes, ({ node }) => 
386
  $isTextNode(node) ? node : null
387
);
388

389
// Transform and filter in one step
390
const headingTexts = $filter(allNodes, ({ node }) => {
391
  if (node.getType() === 'heading') {
392
    return node.getTextContent();
393
  }
394
  return null;
395
});
396
```