Preorder traversal visits a tree node before recursively visiting its children. Starting at the root, it processes the current value, descends through the left subtree, then processes the right subtree. section 3.5
The traversal follows three steps:
- Display or transform the root node’s data. section 3.5
- Recursively traverse the left subtree. section 3.5
- Recursively traverse the right subtree. section 3.5
Mapping a mathematician tree
A Node tree links Church to descendants such as Rosser, Turing, and Kleene. Tree.map(church, p => p.fullname) applies the function during preorder traversal, producing names beginning with Alonzo Church, followed by Barkley Rosser and its children, then the remaining branches. section 3.5
class Tree {
constructor(root) {
this._root = root;
}
static map(node, fn, tree = null) { #1
node.value = fn(node.value); #2
if(tree === null) {
tree = new Tree(node); #3
}
if(node.hasChildren()) { #4
_.map(node.children, function (child) { #5
Tree.map(child, fn, tree); #6
});
}
return tree;
}
get root() {
return this._root;
}
}
Inspect the recursive Tree.map implementation: it transforms the current node, creates the result tree, and recursively maps over each child. section 3.5
