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.

Pre-order traversal

A pre-order traversal in a binary tree consists of:

1. A visit to the node
2. Getting the value
3. A recursion to the left children, if it exists
4. 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 pre-order 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;
}

In-order traversal

An in-order traversal in a binary tree consists of:

1. A visit to the node
2. A recursion to the left children, if it exists
3. Getting the value
4. 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 in-order 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;
}

Post-order traversal

A post-order traversal in a binary tree consists of:

1. A visit to the node
2. A recursion to the left children, if it exists
3. A recursion to the right children, if it exists
4. 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 post-order 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;
}