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;
}