BINARY SEARCH TREES: TRAVERSALS

Josh Raiborde
4 min readDec 12, 2021

--

I’m continuing my learning of the Binary Search Trees, so this post contains notes that I took on Traversals in the Binary Search Tree.

BST are beneficial when you need to access and process large amounts of ordered data very quickly, at the expense of some memory overhead.

Depth First Search (DFS) searches branch by branch, there are three different types of DFS.

The three types of DFS are IN-ORDER, PRE -ORDER and POST-ORDER

Breadth First Search (BFS) searches level by level.

1. INORDER

a. Left Sub Tree

b. Print Node

c. Right Sub Tree

2. PREORDER

a. Print Node

b. Left Sub Tree

c. Right Sub Tree

3. POSTORDER

a. Left Sub Tree

b. Right Sub Tree

c. Print Node

BINARY SEARCH TREES: TRAVERSALS — INORDER

LPR

_______50_______

/ \

LPR LPR

__25__ __75_

/ \ / \

LPR LPR LPR LPR

15 35 65 85

When using INORDER, each node has LPR written over it.

L = Left

P = Print

R = Right

Always start at the root node.

OUTPUT: 15, 25, 35, 50, 65, 75, 85

INORDER outputted in ascending order.

BINARY SEARCH TREES: TRAVERSALS — PREODER

PLR

_______50_______

/ \

PLR PLR

__25__ __75_

/ \ / \

PLR PLR PLR PLR

15 35 65 85

When using PREORDER, each node has PLR written over it.

P = Print

L = Left

R = Right

Always start at the root node.

OUTPUT: 50, 25, 15, 35, 75, 65, 85

BINARY SEARCH TREES: TRAVERSALS — PREODER

LRP

_______50_______

/ \

LRP LRP

__25__ __75_

/ \ / \

LRP LRP LRP LRP

15 35 65 85

When using POSTORDER, each node has LRP written over it.

L = Left

R = Right

P = Print

Always start at the root node.

OUTPUT: 15, 35, 25, 65, 85, 75, 50

BINARY SEARCH TREES: TRAVERSALS — INORDER, PREORDER, POSTORDER

There will be two methods

1. in the BTS class — has no params and will be making the initial call.

2. in the node class.

1. INORDER

a. Left Sub Tree

b. Print Node

c. Right Sub Tree

class BTS {

inorder(){

if(this.root)

// if there is a root node, then we can continue with the INORDER process.

this.root.inorder(this.order)

// if the tree is not empty, then we invoke the inorder method within the Node class, passing in the root node as the starting point.

}

}

class Node {

inorder(currentNode){

if(currentNode){

// if there is a current node, then we can do the following steps:

this.inorder(currentNode.left);

// traverse the left subtree and recursively invoke the inorder method to go left, the left child is passed in.

console.log(currentNode.data);

// print the data at the currentNode

this.inorder(currentNode.right);

// traverse the right subtree and recursively invoke the inorder method to go right, the right child is passed in.

}

}

}

2. PREORDER

a. Print Node

b. Left Sub Tree

c. Right Sub Tree

class BTS{

preorder(){

if(this.root)

// if there is a root node, then we can continue with the PREORDER process.

this.root.preorder(this.order)

// if the tree is not empty, then we invoke the preorder method within the Node class, passing in the root node as the starting point.

}

}

class Node {

preorder(currentNode) {

if(currentNode){

// if there is a current node, then we can do the following steps:

console.log(currentNode.data);

// print the data at the currentNode

this.preorder(currentNode.left);

// traverse the left subtree and recursively invoke the preorder method to go left, the left child is passed in.

this.preorder(currentNode.right);

// traverse the right subtree and recursively invoke the preorder method to go right, the right child is passed in.

}

}

}

3. POSTORDER

a. Left Sub Tree

b. Right Sub Tree

c. Print Node

class BTS{

postorder(){

if(this.root)

// if there is a root node, then we can continue with the POSTORDER process.

this.root.postorder(this.order)

// if the tree is not empty, then we invoke the postorder method within the Node class, passing in the root node as the starting point.

}

}

class Node {

postorder(currentOrder){

if(currentNode){

// if there is a current node, then we can do the following steps:

this.postorder(currentNode.left);

// traverse the left subtree and recursively invoke the postorder method to go left, the left child is passed in.

this.postorder(currentNode.right);

// traverse the right subtree and recursively invoke the postorder method to go right, the right child is passed in.

console.log(currentNode.data);

// print the data at the currentNode

}

}

}

_______50_______

/ \

__25__ __75_

/ \ / \

15 35 65 85

/ \ / \ / \ / \

null null null null null null null null

In conclusion, BST are beneficial when you need to access and process large amounts of ordered data very quickly, at the expense of some memory overhead.

Depth First Search (DFS) searches branch by branch, there are three different types of DFS.

The three types of DFS are IN-ORDER, PRE -ORDER and POST-ORDER

Breadth First Search (BFS) searches level by level.

For now, this is the last post on the Binary Search Tree.

I will move on to learning about other Data Structures.

--

--

Josh Raiborde
Josh Raiborde

Written by Josh Raiborde

Hello, I am a young enthusiastic Software Engineer. Looking forward to an opportunity to use my skills for mutual benefits and growth as well.

No responses yet