Tree traversal is a fundamental concept in computer science that involves systematically visiting each node in a tree data structure. Through tree traversal, we can process the nodes in a predetermined order, facilitating operations like searching, sorting, and evaluating expressions.
In this article, we will explore three of the most widely used tree traversal methods: inorder, preorder, and postorder.
Through clear and concise examples implemented in JavaScript, you will gain a solid understanding of these traversal techniques.
Tree Structure Definition
Before diving into the tree traversal algorithms, let's define the structure we will be using for the binary tree. The tree will consist of nodes, where each node contains a value and references to its left and right child nodes.
function TreeNode(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
Now that we have defined the tree structure, we can proceed with exploring the three tree traversal methods.
Inorder Traversal
Inorder traversal follows the next pattern of visiting nodes in a binary tree - the algorithm first traverses the left subtree, then visits the current node, and finally traverses the right subtree. This ensures that the nodes are visited in ascending order if the tree represents a sorted data structure.
A
/ \
B C
/ \ / \
D E F G
// Inorder traversal result: D -> B -> E -> A -> F -> C -> G
Recursive Inorder Traversal
-
Check if the current node is null. If so, return.
-
Recursively call the function on the left subtree.
-
Visit the current node.
-
Recursively call the function on the right subtree.
function inorderRecursive(tree) {
const result = [];
function inorderTraverse(node) {
if (!node) return;
inorderTraverse(node.left);
result.push(node.val);
inorderTraverse(node.right);
}
inorderTraverse(tree);
return result;
}
Non-recursive Inorder Traversal
-
Initialize an empty stack, and set the current node to the root of the tree.
-
Iterate while the stack is not empty or the current node is not null.
-
Push all left nodes onto the stack until reaching a null left child.
-
Pop a node from the stack, visit it, and set the current node to its right child.
-
-
Repeat step 2 until the stack is empty, and the current node is null.
function inorderRecursive(tree) {
const stack = [];
const result = [];
let currentNode = tree;
while (currentNode || stack.length) {
while (currentNode) {
stack.push(currentNode);
currentNode = currentNode.left;
}
const node = stack.pop();
result.push(node.val);
currentNode = node.right;
}
return result;
}
Preorder Traversal
In preorder traversal, the algorithm first visits the current node, then traverses the left subtree, and finally traverses the right subtree. This ordering ensures that the nodes are visited in a "top-down" manner, starting from the root and moving toward the leaves.
A
/ \
B C
/ \ / \
D E F G
// Preorder traversal result: A -> B -> D -> E -> C -> F -> G
Recursive Preorder Traversal
-
Check if the current node is null. If so, return.
-
Visit the current node.
-
Recursively call the function on the left subtree.
-
Recursively call the function on the right subtree.
function preorderRecursive(tree) {
const result = [];
function preorderTraverse(node) {
if (!node) return;
result.push(node.val);
preorderTraverse(node.left);
preorderTraverse(node.right);
}
preorderTraverse(tree);
return result;
}
Non-recursive Preorder Traversal
-
Start with an empty stack, and push the root node onto the stack.
-
Initialize an empty array to store the preorder traversal result.
-
Enter a while loop that runs until the stack is empty.
-
Pop a node from the stack, and visit it by adding its value to the result array.
-
If the node has a right child, push the right child onto the stack.
-
If the node has a left child, push the left child onto the stack.
-
Repeat steps 3-6 until the stack is empty.
function preorderTraversal(root) {
if (!root) return [];
const stack = [root];
const result = [];
while (stack.length) {
const node = stack.pop();
result.push(node.val);
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}
Postorder Traversal
In this traversal, the algorithm first traverses the left subtree, then the right subtree, and finally visits the current node. This ordering ensures that the nodes are visited in a "bottom-up" manner, starting from the leaves and moving toward the root.
A
/ \
B C
/ \ / \
D E F G
// Postorder traversal result: D -> E -> B -> F -> G -> C -> A
Recursive Postorder Traversal
-
Check if the current node is null. If so, return.
-
Recursively call the function on the left subtree.
-
Recursively call the function on the right subtree.
-
Visit the current node.
function postorderRecursive(tree) {
const result = [];
function postorderTraverse(node) {
if (!node) return;
postorderTraverse(node.left);
postorderTraverse(node.right);
result.push(node.val);
}
postorderTraverse(tree);
return result;
}
Non-recursive Postorder Traversal
-
Start with an empty stack, and push the root node onto the stack.
-
Initialize an empty array to store the postorder traversal result.
-
Enter a while loop that runs until the stack is empty.
-
Get the top node from the stack (without removing it).
-
If the node has a left child, push the left child onto the stack, and set the left child of the current node to null.
-
If the node has a right child, push the right child onto the stack, and set the right child of the current node to null.
-
If the node has neither a left nor a right child, it is a leaf node. Pop the node from the stack, and add its value to the result array.
-
Repeat steps 4-7 until the stack is empty.
function postorderTraversal(root) {
if (!root) return [];
const stack = [root];
const result = [];
while (stack.length) {
const node = stack[stack.length - 1];
if (node.left) {
stack.push(node.left);
node.left = null;
} else if (node.right) {
stack.push(node.right);
node.right = null;
} else {
result.push(stack.pop().val);
}
}
return result;
}
Conclusion
I hope that you now have a clear understanding of the differences between inorder, preorder, and postorder traversal in JavaScript. With the knowledge and examples provided, you are now equipped to apply these techniques to your own tasks and projects effectively.