Tree Traversal

/**
 * Find the inclusive descendant that is last in tree order
 * Time Complexity: O(n) where n is the depth of the subtree
 * @param {Object} object - Starting object
 * @returns {Object} The last descendant in tree order (may be the object itself)
 */
lastInclusiveDescendant(object: Object): Object;

/**
 * Find the preceding object in tree order
 * Time Complexity: O(n) worst case, O(1) amortized when walking entire tree
 * @param {Object} object - Reference object
 * @param {Object} [options] - Traversal options
 * @param {Object} [options.root] - Root boundary for traversal (preceding must be descendant of root)
 * @returns {Object|null} Preceding object or null if none (or outside root boundary)
 */
preceding(object: Object, options?: { root?: Object }): Object | null;

/**
 * Find the following object in tree order
 * Time Complexity: O(n) worst case, O(1) amortized when walking entire tree
 * @param {Object} object - Reference object
 * @param {Object} [options] - Traversal options
 * @param {Object} [options.root] - Root boundary for traversal (following must be descendant of root)
 * @param {boolean} [options.skipChildren=false] - Skip children of the reference object
 * @returns {Object|null} Following object or null if none (or outside root boundary)
 */
following(object: Object, options?: { 
  root?: Object; 
  skipChildren?: boolean; 
}): Object | null;

const SymbolTree = require("symbol-tree");
const tree = new SymbolTree();

// Build a tree:
//     A
//    / \
//   B   E
//  /|   |\
// C D   F G
const nodeA = { name: "A" };
const nodeB = { name: "B" };
const nodeC = { name: "C" };
const nodeD = { name: "D" };
const nodeE = { name: "E" };
const nodeF = { name: "F" };
const nodeG = { name: "G" };

tree.appendChild(nodeA, nodeB);
tree.appendChild(nodeA, nodeE);
tree.appendChild(nodeB, nodeC);
tree.appendChild(nodeB, nodeD);
tree.appendChild(nodeE, nodeF);
tree.appendChild(nodeE, nodeG);

// Tree order: A, B, C, D, E, F, G

// Find last descendant
console.log(tree.lastInclusiveDescendant(nodeA).name); // "G"
console.log(tree.lastInclusiveDescendant(nodeB).name); // "D"
console.log(tree.lastInclusiveDescendant(nodeC).name); // "C" (leaf node)

// Walk forward through entire tree
function walkForward(root) {
  const nodes = [];
  let current = root;
  
  while (current) {
    nodes.push(current.name);
    current = tree.following(current, { root: root });
  }
  
  return nodes;
}

console.log(walkForward(nodeA)); // ["A", "B", "C", "D", "E", "F", "G"]

// Walk backward through entire tree
function walkBackward(root) {
  const nodes = [];
  let current = tree.lastInclusiveDescendant(root);
  
  while (current) {
    nodes.push(current.name);
    current = tree.preceding(current, { root: root });
  }
  
  return nodes;
}

console.log(walkBackward(nodeA)); // ["G", "F", "E", "D", "C", "B", "A"]

// Only traverse within a subtree
const subtreeNodes = [];
let current = nodeB; // Start from B subtree

while (current) {
  subtreeNodes.push(current.name);
  current = tree.following(current, { root: nodeB });
}

console.log(subtreeNodes); // ["B", "C", "D"]

// Skip children of specific nodes
const skipChildrenNodes = [];
current = nodeA;

while (current) {
  skipChildrenNodes.push(current.name);
  
  // Skip children of B (so we won't visit C, D)
  const skipChildren = current === nodeB;
  current = tree.following(current, { 
    root: nodeA, 
    skipChildren: skipChildren 
  });
}

console.log(skipChildrenNodes); // ["A", "B", "E", "F", "G"]

// Find the node that comes right before a specific node
const beforeD = tree.preceding(nodeD);
console.log(beforeD.name); // "C"

// Find the node that comes right after a specific node
const afterD = tree.following(nodeD);
console.log(afterD.name); // "E"

// Find preceding within a subtree only
const beforeF = tree.preceding(nodeF, { root: nodeE });
console.log(beforeF.name); // "E"

// If we used no root boundary:
const beforeFGlobal = tree.preceding(nodeF);
console.log(beforeFGlobal.name); // "D" (from outside the E subtree)

function traverseTree(startNode, options = {}) {
  const { 
    root = null, 
    skipChildren = false, 
    direction = "forward" 
  } = options;
  
  const result = [];
  let current = startNode;
  
  if (direction === "forward") {
    while (current) {
      result.push(current);
      current = tree.following(current, { 
        root: root, 
        skipChildren: current === startNode ? skipChildren : false 
      });
    }
  } else {
    // Start from last descendant for backward traversal
    current = root ? tree.lastInclusiveDescendant(startNode) : startNode;
    while (current) {
      result.push(current);
      current = tree.preceding(current, { root: root });
    }
  }
  
  return result;
}

// Usage examples
const allNodes = traverseTree(nodeA).map(n => n.name);
console.log(allNodes); // ["A", "B", "C", "D", "E", "F", "G"]

const subtreeOnly = traverseTree(nodeE, { root: nodeE }).map(n => n.name);
console.log(subtreeOnly); // ["E", "F", "G"]

const skipBChildren = traverseTree(nodeA, { skipChildren: true }).map(n => n.name);
console.log(skipBChildren); // ["A"] (skips all descendants)

// Simulate DOM tree walking patterns
function findNextTextNode(currentNode, root) {
  let next = tree.following(currentNode, { root: root });
  
  while (next && next.nodeType !== "text") {
    next = tree.following(next, { root: root });
  }
  
  return next;
}

function findPreviousElement(currentNode, root) {
  let prev = tree.preceding(currentNode, { root: root });
  
  while (prev && prev.nodeType !== "element") {
    prev = tree.preceding(prev, { root: root });
  }
  
  return prev;
}