Binary Search Trees III/? - Traversal

Alright, down to business. In our ongoing discussion of Binary Search Trees, we've come to traversal! I know, I know, last time I said this would be about adding and removing nodes. But! Looks like I was getting ahead of myself. It didn't occur to me that in order to properly add, we would need to traverse the tree to find the appropriate spot!

So we'll take a look at how to traverse through a tree to find a particular node. The below methods are all Depth-First traversal methods, meaning the branches are examined top to bottom or bottom to top. This is as opposed to Breadth-First which examines each node in a level.

Traversing through the tree involves "visiting" or "touching" each node as you go. Translating that to code, that means running some code on the node, such as checking for equality or printing it out. There are three depth-first methods, In-Order, Pre-Order, and Post-Order Traversal.

In-Order Traversal

In-Order Traversal refers to visiting each node on the branch to the left of the current node, then the current node, then each node on the branch to the right. This is best executed with recursion. Let's take a look.

We'll set up a function that takes in our "current" node. First, we'll want to couch everything in an if statement checking whether or not the node is null, since that would mean there's no traversing to be done.

function inOrderTraversal(node){
    if (node != null){
        // do stuff
    }
}

Let's plug in the root node for the below tree.

We're now looking at a node with data 0 and two children. From there what's next? We'll want to look at that node's left child. So what do we do? We call the function again on the child!

function inOrderTraversal(node){
    if (node != null){
        inOrderTraversal(node.left);
        // do more stuff
    }
}

This process will repeat until we reach the bottom level, the one composed of leaf nodes - that's the recursion at work. In this case we hit the "3" node, and the recursion stops (node.left of the 3 node will be null). So what now? It's time to start performing whatever action we wanted to do in the first place. Let's say we're determining if the number "25" is in the tree, and if it is we will perform some unspecified action.

function inOrderTraversal(node){
    if (node != null){
        inOrderTraversal(node.left);
        if (node.data == 25){
            // do stuff
        };
        // do more stuff
    }
}

If the data in the current node matches our target, 25, we'll return that node and be done. Since it doesn't though, we'll want to move on and look to the right.

function inOrderTraversal(node){
    if (node != null){
        inOrderTraversal(node.left);
        if (node.data == 25){
            // do stuff
        };
        inOrderTraversal(node.right);
    }
}

That's the full traversal function. It will visit the nodes in ascending order, from left to right. That's why it's In Order Traversal!

Pre-Order Traversal

Now that we've done one type of traversal, it should be fairly easy to interpret what's going on in the next two types. Pre-Order traversal visits the current node before both of its child nodes (unlike In-Order, which visited left child, current node, then right child). Here's a function for Pre-Order Traversal:

function preOrderTraversal(node){
    if (node != null){
        visit(node);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

As you can see, it's essentially the same function, with merely the order swapped around. The visit() function here is standing in for our equality comparison and // do stuff comments above.

That's the full function. In Pre-Order traversal, the root is always the first node visited. This could also be thought of as top to bottom.

Post-Order Traversal

Last is Post-Order Traversal, where the root is examined last. The current node is visited after its children.

function postOrderTraversal(node){
    if (node != null){
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        visit(node);
    }
}

This could be thought of as bottom to top.

See how those second two were a breeze after the first one?