Transversing Binary Search Trees

3 min readOct 24, 2020

Transversing a Binary Search Tree has to be a separate topic because there’s so many ways to accomplish this, we have to discuss this topic at length.

This topic is a continuation of last week topic “Binary Search Trees”. With that being said this isn’t the article were we’re going to explain them and I will continue calling them “BST”. Also, we will be using lots of recursion in this post, so I recommend the article on Recursion before starting this one.

By transversing a binary search tree we visit each node once. There’s two common ways we do this either by Breadth-first Search or Depth-first Search. Breadth-first is working across the tree and Depth-first is working the tree vertically.

If we were to compare them we have to consider the shape of the tree and the impact the shape has on the space complexity. We consider space complexity over time complexity because we are visiting each node once so the time complexity is virtually the same. So if the tree is wider than long/deep, we use depth-first searching which, saves less items in the queue which we will discuss later on.

There are three different ways we can do depth first searching: PreOrder, InOrder and PostOrder. These three are different based on the placement of a single line of code. InOrder returns the items in our BST in order from lowest to highest and PreOrder is returns the items in order from root down which is useful if we are cloning/reconstructing the data.

Code for Breadth-First Search

BFS(){// Create a queue and a variable to store the values of nodes visited
        var node = this.root,
            data = [],
            queue = [];// Place the root node in the queue
        queue.push(node);// Loop as long as there is anything in the queue
        while(queue.length){// Dequeue a node from the queue and push the value of the node into the variable that stores the nodes
           node = queue.shift();
           data.push(node.value);// If there is a left property on the node dequeued - add it to the queue
           if(node.left) queue.push(node.left);// If there is a right property on the node dequeued - add it to the queue
           if(node.right) queue.push(node.right);
        }// Return the variable that stores the values.
        return data;
    }

Code for Depth-First Searching:

PreOrder: Visiting the node and look at the left and right. What we are doing Recursively is visiting a node then, we visit the entire left side and the entire right side.

DFSPreOrder(){// Create a variable to store the values of nodes visited
        var data = [];// Write a helper function which accepts a node
        function traverse(node){// Push the value of the node to the variable that stores the values
            data.push(node.value);// If the node has a left property, call the helper function with the left property on the node
            if(node.left) traverse(node.left);// If the node has a right property, call the helper function with the right property on the node
            if(node.right) traverse(node.right);
        }// Invoke the helper function with the current variable
       traverse(this.root);// 
        return data;
    }

PostOrder: Pseudo Code everything is the same as the Pre Order, But in a different order.

DFSPostOrder(){// Create a variable to store the values of nodes visited
        var data = [];// Write a helper function which accepts a node
        function traverse(node){// If the node has a left property, call the helper function with the left property on the node
            if(node.left) traverse(node.left);// If the node has a right property, call the helper function with the right property on the node
            if(node.right) traverse(node.right);// Push the value of the node to the variable that stores the values. The placement of this line is what makes it Post order.
            data.push(node.value);
        }// Invoke the helper function with the current variable
        traverse(this.root);// Return the array of values
        return data;
    }

In Order :

DFSInOrder(){
        var data = [];// Transversing the entire left side then visiting the node and then traversing the entire right side
        function traverse(node){
            if(node.left) traverse(node.left);// Every node, we transverse the left then we visit the node then we transverse the right
            data.push(node.value);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }

This wraps up our section on Binary Search Trees. Thanks for reading!

Transversing Binary Search Trees

Written by Keenan Jones