Overview
In coding tests, various data structure and algorithm problems are presented. Among them, trees are a commonly occurring data structure.
Tree structures play a very important role in computer science and are utilized in various fields such as file systems and databases.
In this course, we will learn how to traverse trees using JavaScript.
What is a Tree Structure?
A tree is a nonlinear data structure composed of nodes and edges, optimized for representing hierarchical relationships.
A tree has concepts such as root node, child node, parent node, and leaf node.
The main characteristics of a tree are as follows:
- A tree has one root, and child nodes are connected from this root.
- A node can have zero or more child nodes.
- A leaf node is a node that has no children.
Tree Traversal Methods
There are several ways to traverse a tree, with the most commonly used methods being:
- Pre-order Traversal
- In-order Traversal
- Post-order Traversal
- Level-order Traversal
The order in which nodes are visited differs for each traversal method. Let’s take a closer look at each method.
Pre-order Traversal
The method of pre-order traversal is as follows:
- Visit the current node.
- Traverse the left subtree in pre-order.
- Traverse the right subtree in pre-order.
For example, suppose we have the following tree structure.
Public
├── User 1
│ ├── User 1.1
│ └── User 1.2
└── User 2
├── User 2.1
└── User 2.2
The result of the pre-order traversal is “Public, User 1, User 1.1, User 1.2, User 2, User 2.1, User 2.2”.
In-order Traversal
The method of in-order traversal is as follows:
- Traverse the left subtree in in-order.
- Visit the current node.
- Traverse the right subtree in in-order.
For example, in the same tree structure, the result of the in-order traversal is “User 1.1, User 1, User 1.2, Public, User 2.1, User 2, User 2.2”.
Post-order Traversal
The method of post-order traversal is as follows:
- Traverse the left subtree in post-order.
- Traverse the right subtree in post-order.
- Visit the current node.
In the same tree structure, the result of the post-order traversal is “User 1.1, User 1.2, User 1, User 2.1, User 2.2, User 2, Public”.
Level-order Traversal
The method of level-order traversal is as follows:
- Visit the root node.
- Visit the child nodes of the current node.
- After visiting all child nodes, move to the next depth.
In the same tree structure, the result of the level-order traversal is “Public, User 1, User 2, User 1.1, User 1.2, User 2.1, User 2.2”.
Programming Problem: Binary Tree Traversal
Given the following binary tree structure, write a function to traverse the tree using various traversal methods.
A binary tree is composed of nodes structured as follows:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
Example Input:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
Problem
Write a function for pre-order, in-order, post-order, and level-order traversal of the binary tree above.
Problem Solving Process
1. Implementing Pre-order Traversal
To perform pre-order traversal, a recursive approach is needed. Below is the code that implements this:
function preOrderTraversal(node) {
if (node === null) return;
console.log(node.value); // Visit current node
preOrderTraversal(node.left); // Visit left subtree
preOrderTraversal(node.right); // Visit right subtree
}
The above code visits the current node first and then traverses the left and right nodes.
2. Implementing In-order Traversal
In-order traversal is also implemented recursively. Below is the in-order traversal code:
function inOrderTraversal(node) {
if (node === null) return;
inOrderTraversal(node.left); // Visit left subtree
console.log(node.value); // Visit current node
inOrderTraversal(node.right); // Visit right subtree
}
This code visits the left subtree first and then the current node.
3. Implementing Post-order Traversal
Post-order traversal is also implemented recursively. Below is the implemented code:
function postOrderTraversal(node) {
if (node === null) return;
postOrderTraversal(node.left); // Visit left subtree
postOrderTraversal(node.right); // Visit right subtree
console.log(node.value); // Visit current node
}
In post-order traversal, the current node is visited after both child subtrees.
4. Implementing Level-order Traversal
Level-order traversal is implemented using a queue data structure. By using a queue, each node can be visited layer by layer. Below is the level-order traversal code:
function levelOrderTraversal(root) {
if (root === null) return;
const queue = [root]; // Initialize the queue
while (queue.length > 0) {
const current = queue.shift(); // Remove node from the queue
console.log(current.value); // Visit current node
if (current.left) queue.push(current.left); // Add left child
if (current.right) queue.push(current.right); // Add right child
}
}
Using a queue allows each node to be visited in order by level.
Conclusion
In this course, we explored various methods of traversing trees using JavaScript.
Tree traversal is a fundamental part of many programming problems, so it’s important to practice sufficiently.
Understanding and implementing the pre-order, in-order, post-order, and level-order traversal algorithms covered above is a great way to achieve good results in coding tests.
Continue to solve various algorithm problems through practice. Practice and repetition are the best teachers!