Tree traversal is the process of visiting and processing each node in a tree data structure. There are two main types of tree traversal: depth-first traversal and breadth-first traversal.
Depth-First Traversal
In depth-first traversal, we visit each node in a tree starting from the root node and recursively visiting its child nodes before moving on to its siblings. There are three different ways to perform depth-first traversal: in-order, pre-order, and post-order.
In-order traversal visits the left subtree, the root node, and then the right subtree.
Pre-order traversal visits the root node, then the left subtree, and then the right subtree.
Post-order traversal visits the left subtree, the right subtree, and then the root node.
In-Order Traversal
In-order traversal is a depth-first traversal method that visits the left subtree, then the root node, and then the right subtree of a tree. Here is an example of how to perform in-order traversal on a binary search tree in JavaScript:
// Define the node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Define the BST class
class BST {
constructor() {
this.root = null;
}
// Insert a new node in tree
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return undefined;
}
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
// Perform in-order traversal of the tree
inOrderTraversal(node = this.root, result = []) {
if (node) {
this.inOrderTraversal(node.left, result);
result.push(node.value);
this.inOrderTraversal(node.right, result);
}
return result;
}
}
// Create a binary search tree and insert some nodes
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
// Perform in-order traversal and print the result
console.log("In-order Traversal: " + bst.inOrderTraversal());
In the code above, we define a Node class to represent each node in the tree and a BST class to represent the binary search tree. We implement the insert method to insert new nodes into the tree, and the inOrderTraversal method to perform in-order traversal of the tree.
In the inOrderTraversal method, we recursively traverse the left subtree, visit the root node, and then recursively traverse the right subtree. We use an array result to store the values of the nodes visited during traversal and return it at the end.
Finally, we create a binary search tree, insert some nodes, and call the inOrderTraversal method to perform in-order traversal of the tree. The output of this traversal is [3, 5, 7, 10, 12, 15, 17], which represents the values of the nodes visited in the order of traversal.
In-order Traversal: 3,5,7,10,12,15,17
Pre-Order Traversal
Pre-order traversal is a type of tree traversal algorithm that visits each node in the tree starting from the root, and then recursively traverses the left and right subtrees. In pre-order traversal, the current node is visited first, followed by its left subtree, and then its right subtree.
Here is an example implementation of pre-order traversal in JavaScript:
// Define the node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Define the binary search tree class
class BST {
constructor() {
this.root = null;
}
// Insert a new node into the tree
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return undefined;
}
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
// Perform pre-order traversal of the tree
preOrderTraversal(node = this.root, result = []) {
if (node) {
result.push(node.value);
this.preOrderTraversal(node.left, result);
this.preOrderTraversal(node.right, result);
}
return result;
}
}
// Create a binary search tree and insert some nodes
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
// Perform pre-order traversal and display the results
console.log("Pre-order Traversal: " + bst.preOrderTraversal());
In this example, we define a preOrderTraversal method for the BST class that performs pre-order traversal of the tree. The method takes two arguments: node is the current node being visited, and result is an array that stores the values of the nodes visited so far.
The implementation of preOrderTraversal method is as follows:
Check if the
nodeexists, if yes, then:Add the value of the
nodeto theresultarray.Recursively traverse the left subtree by calling
preOrderTraversalmethod with thenode's left child as the newnode.Recursively traverse the right subtree by calling
preOrderTraversalmethod with thenode's right child as the newnode.
In the end, the method returns the result array with the values of all nodes in the tree, visited in pre-order traversal.
When we run this code, it outputs the following:
Pre-order Traversal: 10,5,3,7,15,12,17
This is the pre-order traversal of the binary search tree we created earlier. The first value in the output is the value of the root node, followed by the values of the left and right subtrees, visited in pre-order.
Post-Order Traversal
Post-order traversal is a type of tree traversal algorithm that visits each node in the tree recursively, starting from the leftmost node of the tree and then visiting the right subtree followed by the root node. In post-order traversal, the current node is visited last, after its left and right subtrees have been visited.
Here is an example implementation of post-order traversal in JavaScript:
// Define the node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Define the binary search tree class
class BST {
constructor() {
this.root = null;
}
// Insert a new node into the tree
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return undefined;
}
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
// Perform post-order traversal of the tree
postOrderTraversal(node = this.root, result = []) {
if (node) {
this.postOrderTraversal(node.left, result);
this.postOrderTraversal(node.right, result);
result.push(node.value);
}
return result;
}
}
// Create a binary search tree and insert some nodes
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
// Perform post-order traversal and display the results
console.log("Post-order Traversal: " + bst.postOrderTraversal());
In this example, we define a postOrderTraversal method for the BST class that performs post-order traversal of the tree. The method takes two arguments: node is the current node being visited, and result is an array that stores the values of the nodes visited so far.
The implementation of postOrderTraversal method is as follows:
Check if the
nodeexists, if yes, then:Recursively traverse the left subtree by calling
postOrderTraversalmethod with thenode's left child as the newnode.Recursively traverse the right subtree by calling
postOrderTraversalmethod with thenode's right child as the newnode.Add the value of the
nodeto theresultarray.
In the end, the method returns the result array with the values of all nodes in the tree, visited in post-order traversal.
When we run this code, it outputs the following:
Post-order Traversal: 3,7,5,12,17,15,10
This is the post-order traversal of the binary search tree we created earlier. The first values in the output are the values of the leaf nodes of the tree, followed by the values of the internal nodes, visited in post-order. Finally, the output ends with the value of the root node.
Breadth-First Traversal
In breadth-first traversal, we visit each level of the tree from left to right before moving on to the next level. This is achieved by visiting all the nodes at a given level before moving on to the next level.
// Define the node class
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Define the binary search tree class
class BST {
constructor() {
this.root = null;
}
// Insert a new node into the tree
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (value === current.value) {
return undefined;
}
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
// Perform breadth-first traversal of the tree
breadthFirstTraversal() {
const queue = [];
const result = [];
if (this.root) {
queue.push(this.root);
while (queue.length > 0) {
const current = queue.shift();
result.push(current.value);
if (current.left) {
queue.push(current.left);
}
if (current.right) {
queue.push(current.right);
}
}
}
return result;
}
}
// Create a binary search tree and insert some nodes
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);
// Perform breadth-first traversal and display the results
console.log("Breadth-First Traversal: " + bst.breadthFirstTraversal());
In this example, we define a breadthFirstTraversal method for the BST class that performs breadth-first traversal of the tree. The method uses a queue to keep track of the nodes to be visited. We start by pushing the root node onto the queue, then we iterate through the queue until it is empty. For each node in the queue, we add its value to the result array and push its children onto the queue.
In the end, the method returns the result array with the values of all nodes in the tree, visited in breadth-first traversal.
When we run this code, it outputs the following:
Breadth-First Traversal: 10,5,15,3,7,12,17
This is the breadth-first traversal of the binary search tree we created earlier. The output lists the values of all nodes in the tree, visited in the order they were explored. The first value in the output is the value of the root node, followed by the values of all the nodes at the first level, then all the nodes at the second level, and so on.
Summarizing Up
Traversal is a fundamental operation in working with trees and is used in many algorithms, such as searching for a specific value in a tree or printing the contents of a tree in a specific order.
Tree traversal is the process of visiting every node in a tree data structure exactly once in a specific order. There are several types of tree traversal algorithms, including depth-first and breadth-first traversal. Depth-first traversal includes pre-order, in-order, and post-order traversals. Breadth-first traversal visits all the nodes at the current level before moving to the next level. Each traversal algorithm has a different order in which nodes are visited. Traversal algorithms are commonly used in tree data structures to search for and retrieve data, as well as to manipulate and transform the structure of the tree.