0
# Tree Traversal
1
2
Advanced traversal operations for finding preceding/following objects and tree boundaries.
3
4
## Capabilities
5
6
### Last Inclusive Descendant
7
8
Find the last descendant of an object in tree order.
9
10
```javascript { .api }
11
/**
12
* Find the inclusive descendant that is last in tree order
13
* Time Complexity: O(n) where n is the depth of the subtree
14
* @param {Object} object - Starting object
15
* @returns {Object} The last descendant in tree order (may be the object itself)
16
*/
17
lastInclusiveDescendant(object: Object): Object;
18
```
19
20
### Preceding Object
21
22
Find the object that comes before the given object in tree order.
23
24
```javascript { .api }
25
/**
26
* Find the preceding object in tree order
27
* Time Complexity: O(n) worst case, O(1) amortized when walking entire tree
28
* @param {Object} object - Reference object
29
* @param {Object} [options] - Traversal options
30
* @param {Object} [options.root] - Root boundary for traversal (preceding must be descendant of root)
31
* @returns {Object|null} Preceding object or null if none (or outside root boundary)
32
*/
33
preceding(object: Object, options?: { root?: Object }): Object | null;
34
```
35
36
### Following Object
37
38
Find the object that comes after the given object in tree order.
39
40
```javascript { .api }
41
/**
42
* Find the following object in tree order
43
* Time Complexity: O(n) worst case, O(1) amortized when walking entire tree
44
* @param {Object} object - Reference object
45
* @param {Object} [options] - Traversal options
46
* @param {Object} [options.root] - Root boundary for traversal (following must be descendant of root)
47
* @param {boolean} [options.skipChildren=false] - Skip children of the reference object
48
* @returns {Object|null} Following object or null if none (or outside root boundary)
49
*/
50
following(object: Object, options?: {
51
root?: Object;
52
skipChildren?: boolean;
53
}): Object | null;
54
```
55
56
## Usage Examples
57
58
### Tree Order Traversal
59
60
Tree order follows a depth-first pattern where each node appears before its descendants:
61
62
```javascript
63
const SymbolTree = require("symbol-tree");
64
const tree = new SymbolTree();
65
66
// Build a tree:
67
// A
68
// / \
69
// B E
70
// /| |\
71
// C D F G
72
const nodeA = { name: "A" };
73
const nodeB = { name: "B" };
74
const nodeC = { name: "C" };
75
const nodeD = { name: "D" };
76
const nodeE = { name: "E" };
77
const nodeF = { name: "F" };
78
const nodeG = { name: "G" };
79
80
tree.appendChild(nodeA, nodeB);
81
tree.appendChild(nodeA, nodeE);
82
tree.appendChild(nodeB, nodeC);
83
tree.appendChild(nodeB, nodeD);
84
tree.appendChild(nodeE, nodeF);
85
tree.appendChild(nodeE, nodeG);
86
87
// Tree order: A, B, C, D, E, F, G
88
89
// Find last descendant
90
console.log(tree.lastInclusiveDescendant(nodeA).name); // "G"
91
console.log(tree.lastInclusiveDescendant(nodeB).name); // "D"
92
console.log(tree.lastInclusiveDescendant(nodeC).name); // "C" (leaf node)
93
```
94
95
### Walking Tree in Order
96
97
```javascript
98
// Walk forward through entire tree
99
function walkForward(root) {
100
const nodes = [];
101
let current = root;
102
103
while (current) {
104
nodes.push(current.name);
105
current = tree.following(current, { root: root });
106
}
107
108
return nodes;
109
}
110
111
console.log(walkForward(nodeA)); // ["A", "B", "C", "D", "E", "F", "G"]
112
113
// Walk backward through entire tree
114
function walkBackward(root) {
115
const nodes = [];
116
let current = tree.lastInclusiveDescendant(root);
117
118
while (current) {
119
nodes.push(current.name);
120
current = tree.preceding(current, { root: root });
121
}
122
123
return nodes;
124
}
125
126
console.log(walkBackward(nodeA)); // ["G", "F", "E", "D", "C", "B", "A"]
127
```
128
129
### Subtree Traversal with Root Boundaries
130
131
```javascript
132
// Only traverse within a subtree
133
const subtreeNodes = [];
134
let current = nodeB; // Start from B subtree
135
136
while (current) {
137
subtreeNodes.push(current.name);
138
current = tree.following(current, { root: nodeB });
139
}
140
141
console.log(subtreeNodes); // ["B", "C", "D"]
142
143
// Skip children of specific nodes
144
const skipChildrenNodes = [];
145
current = nodeA;
146
147
while (current) {
148
skipChildrenNodes.push(current.name);
149
150
// Skip children of B (so we won't visit C, D)
151
const skipChildren = current === nodeB;
152
current = tree.following(current, {
153
root: nodeA,
154
skipChildren: skipChildren
155
});
156
}
157
158
console.log(skipChildrenNodes); // ["A", "B", "E", "F", "G"]
159
```
160
161
### Finding Adjacent Nodes
162
163
```javascript
164
// Find the node that comes right before a specific node
165
const beforeD = tree.preceding(nodeD);
166
console.log(beforeD.name); // "C"
167
168
// Find the node that comes right after a specific node
169
const afterD = tree.following(nodeD);
170
console.log(afterD.name); // "E"
171
172
// Find preceding within a subtree only
173
const beforeF = tree.preceding(nodeF, { root: nodeE });
174
console.log(beforeF.name); // "E"
175
176
// If we used no root boundary:
177
const beforeFGlobal = tree.preceding(nodeF);
178
console.log(beforeFGlobal.name); // "D" (from outside the E subtree)
179
```
180
181
### Practical Tree Walking Function
182
183
```javascript
184
function traverseTree(startNode, options = {}) {
185
const {
186
root = null,
187
skipChildren = false,
188
direction = "forward"
189
} = options;
190
191
const result = [];
192
let current = startNode;
193
194
if (direction === "forward") {
195
while (current) {
196
result.push(current);
197
current = tree.following(current, {
198
root: root,
199
skipChildren: current === startNode ? skipChildren : false
200
});
201
}
202
} else {
203
// Start from last descendant for backward traversal
204
current = root ? tree.lastInclusiveDescendant(startNode) : startNode;
205
while (current) {
206
result.push(current);
207
current = tree.preceding(current, { root: root });
208
}
209
}
210
211
return result;
212
}
213
214
// Usage examples
215
const allNodes = traverseTree(nodeA).map(n => n.name);
216
console.log(allNodes); // ["A", "B", "C", "D", "E", "F", "G"]
217
218
const subtreeOnly = traverseTree(nodeE, { root: nodeE }).map(n => n.name);
219
console.log(subtreeOnly); // ["E", "F", "G"]
220
221
const skipBChildren = traverseTree(nodeA, { skipChildren: true }).map(n => n.name);
222
console.log(skipBChildren); // ["A"] (skips all descendants)
223
```
224
225
### DOM-Style Tree Walking
226
227
```javascript
228
// Simulate DOM tree walking patterns
229
function findNextTextNode(currentNode, root) {
230
let next = tree.following(currentNode, { root: root });
231
232
while (next && next.nodeType !== "text") {
233
next = tree.following(next, { root: root });
234
}
235
236
return next;
237
}
238
239
function findPreviousElement(currentNode, root) {
240
let prev = tree.preceding(currentNode, { root: root });
241
242
while (prev && prev.nodeType !== "element") {
243
prev = tree.preceding(prev, { root: root });
244
}
245
246
return prev;
247
}
248
```