Tree Traversal

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

interface DFSNode {
  readonly depth: number;
  readonly node: LexicalNode;
}

import { $dfs } from "@lexical/utils";
import { $getRoot } from "lexical";

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

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

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

// Find all text nodes in document
const textNodes = $dfs()
  .filter(({ node }) => node.getType() === 'text')
  .map(({ node }) => node);

/**
 * $dfs iterator (left to right). Tree traversal is done on the fly as new values are requested with O(1) memory.
 * @param startNode - The node to start the search, if omitted, it will start at the root node.
 * @param endNode - The node to end the search, if omitted, it will find all descendants of the startingNode.
 * @returns An iterator, each yielded value is a DFSNode. It will always return at least 1 node (the start node).
 */
function $dfsIterator(
  startNode?: LexicalNode,
  endNode?: LexicalNode
): IterableIterator<DFSNode>;

import { $dfsIterator } from "@lexical/utils";

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

// Process nodes in chunks
const iterator = $dfsIterator();
const batch: DFSNode[] = [];
for (const dfsNode of iterator) {
  batch.push(dfsNode);
  if (batch.length === 10) {
    // Process batch of 10 nodes
    processBatch(batch);
    batch.length = 0;
  }
}

/**
 * Performs a right-to-left preorder tree traversal.
 * From the starting node it goes to the rightmost child, than backtracks to parent and finds new rightmost path.
 * @param startNode - The node to start the search, if omitted, it will start at the root node.
 * @param endNode - The node to end the search, if omitted, it will find all descendants of the startingNode.
 * @returns An array of DFSNode objects in reverse traversal order.
 */
function $reverseDfs(
  startNode?: LexicalNode,
  endNode?: LexicalNode
): Array<DFSNode>;

function $reverseDfsIterator(
  startNode?: LexicalNode,
  endNode?: LexicalNode
): IterableIterator<DFSNode>;

/**
 * Get the adjacent caret in the same direction
 * @param caret - A caret or null
 * @returns caret.getAdjacentCaret() or null
 */
function $getAdjacentCaret<D extends CaretDirection>(
  caret: null | NodeCaret<D>
): null | SiblingCaret<LexicalNode, D>;

/**
 * Calculates depth of a node in the tree
 * @param node - The node to calculate depth for
 * @returns The depth level (0 for root)
 */
function $getDepth(node: null | LexicalNode): number;

import { $getDepth } from "@lexical/utils";

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

// Use depth for indentation or styling
if (depth > 3) {
  // Apply deep nesting styles
  addClassNamesToElement(element, 'deeply-nested');
}

/**
 * Returns the Node sibling when this exists, otherwise the closest parent sibling. For example
 * R -> P -> T1, T2
 *   -> P2
 * returns T2 for node T1, P2 for node T2, and null for node P2.
 * @param node - LexicalNode.
 * @returns An array (tuple) containing the found Lexical node and the depth difference, or null, if this node doesn't exist.
 */
function $getNextSiblingOrParentSibling(
  node: LexicalNode
): null | [LexicalNode, number];

/**
 * Performs a right-to-left preorder tree traversal.
 * From the starting node it goes to the rightmost child, than backtracks to parent and finds new rightmost path.
 * It will return the next node in traversal sequence after the startingNode.
 * The traversal is similar to $dfs functions above, but the nodes are visited right-to-left, not left-to-right.
 * @param startingNode - The node to start the search.
 * @returns The next node in pre-order right to left traversal sequence or null, if the node does not exist
 */
function $getNextRightPreorderNode(
  startingNode: LexicalNode
): LexicalNode | null;

/**
 * Takes a node and traverses up its ancestors (toward the root node)
 * in order to find a specific type of node.
 * @param node - the node to begin searching.
 * @param klass - an instance of the type of node to look for.
 * @returns the node of type klass that was passed, or null if none exist.
 */
function $getNearestNodeOfType<T extends ElementNode>(
  node: LexicalNode,
  klass: Klass<T>
): T | null;

import { $getNearestNodeOfType } from "@lexical/utils";
import { ListNode, ListItemNode } from "@lexical/list";

const currentNode = $getSelection()?.getNodes()[0];
if (currentNode) {
  // Find containing list
  const listNode = $getNearestNodeOfType(currentNode, ListNode);
  if (listNode) {
    console.log('Inside a list:', listNode.getListType());
  }
  
  // Find containing list item
  const listItemNode = $getNearestNodeOfType(currentNode, ListItemNode);
  if (listItemNode) {
    console.log('Inside list item:', listItemNode.getValue());
  }
}

/**
 * Returns the element node of the nearest ancestor, otherwise throws an error.
 * @param startNode - The starting node of the search
 * @returns The ancestor node found
 */
function $getNearestBlockElementAncestorOrThrow(
  startNode: LexicalNode
): ElementNode;

/**
 * Starts with a node and moves up the tree (toward the root node) to find a matching node based on
 * the search parameters of the findFn. (Consider JavaScripts' .find() function where a testing function must be
 * passed as an argument. eg. if( (node) => node.__type === 'div') ) return true; otherwise return false
 * @param startingNode - The node where the search starts.
 * @param findFn - A testing function that returns true if the current node satisfies the testing parameters.
 * @returns A parent node that matches the findFn parameters, or null if one wasn't found.
 */
function $findMatchingParent<T extends LexicalNode>(
  startingNode: LexicalNode,
  findFn: (node: LexicalNode) => node is T
): T | null;
function $findMatchingParent(
  startingNode: LexicalNode,
  findFn: (node: LexicalNode) => boolean
): LexicalNode | null;

import { $findMatchingParent } from "@lexical/utils";

const currentNode = $getSelection()?.getNodes()[0];
if (currentNode) {
  // Find nearest editable element
  const editableParent = $findMatchingParent(
    currentNode,
    (node) => $isElementNode(node) && node.isEditable()
  );
  
  // Find nearest node with specific attribute
  const styledParent = $findMatchingParent(
    currentNode,
    (node) => node.hasFormat('bold')
  );
  
  // Type-safe search with type predicate
  const tableParent = $findMatchingParent(
    currentNode,
    (node): node is TableNode => node instanceof TableNode
  );
}

/**
 * Return an iterator that yields each child of node from first to last, taking
 * care to preserve the next sibling before yielding the value in case the caller
 * removes the yielded node.
 * @param node - The node whose children to iterate
 * @returns An iterator of the node's children
 */
function $firstToLastIterator(node: ElementNode): Iterable<LexicalNode>;

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

import { $firstToLastIterator, $lastToFirstIterator } from "@lexical/utils";

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

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

// Safe backward iteration
for (const child of $lastToFirstIterator(parentElement)) {
  if (shouldProcessChild(child)) {
    processChild(child);
  }
}

/**
 * Filter the nodes
 * @param nodes - Array of nodes that needs to be filtered
 * @param filterFn - A filter function that returns node if the current node satisfies the condition otherwise null
 * @returns Array of filtered nodes
 */
function $filter<T>(
  nodes: Array<LexicalNode>,
  filterFn: (node: LexicalNode) => null | T
): Array<T>;

import { $filter, $dfs } from "@lexical/utils";
import { $isTextNode } from "lexical";

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

// Transform and filter in one step
const headingTexts = $filter(allNodes, ({ node }) => {
  if (node.getType() === 'heading') {
    return node.getTextContent();
  }
  return null;
});