Tree Search Algorithms
When working in trees, moving inside the structure is often called traversal. The algorithms described below could there be considered traversal algorithms.
Depth First Search
Below are examples of traversals of what is called Depth First Search (DFS), because the traversal happens vertically or depth first.
Preorder traversal
A preorder traversal in a binary tree consists of:
 A visit to the node
 Getting the value
 A recursion to the left children, if it exists
 A recursion to the right children, if it exists
7


23 3
 
 
   
5 4 18 21
The order of recursion will be 7, 23, 5, 4, 3, 18, 21. In a preorder transversal, the root is at the beginning.
Example:
export default function pre_order_search(head: BinaryNode<number>): number[] {
return walk(head, path);
}
function walk(curr: BinaryNode<number>  null, path:number[]): void {
if (!curr) {
return path;
}
path.push(curr.value);
walk(curr.left, path);
walk(curr.right, path);
return path;
}
Inorder traversal
An inorder traversal in a binary tree consists of:
 A visit to the node
 A recursion to the left children, if it exists
 Getting the value
 A recursion to the right children, if it exists
7


23 3
 
 
   
5 4 18 21
The order of recursion will be 5, 23, 4, 7, 18, 3, 21. In a inorder transversal, the root is in the middle.
Example:
export default function in_order_search(head: BinaryNode<number>): number[] {
return walk(head, path);
}
function walk(curr: BinaryNode<number>  null, path:number[]): void {
if (!curr) {
return path;
}
walk(curr.left, path);
path.push(curr.value);
walk(curr.right, path);
return path;
}
Postorder traversal
A postorder traversal in a binary tree consists of:
 A visit to the node
 A recursion to the left children, if it exists
 A recursion to the right children, if it exists
 Getting the value
7


23 3
 
 
   
5 4 18 21
The order of recursion will be 5, 4, 23, 18, 21, 3, 7. In an postorder transversal, the root is at the end.
Example:
export default function post_order_search(head: BinaryNode<number>): number[] {
return walk(head, path);
}
function walk(curr: BinaryNode<number>  null, path:number[]): void {
if (!curr) {
return path;
}
walk(curr.left, path);
walk(curr.right, path);
path.push(curr.value);
return path;
}
Generated: March 22nd, 2023