Tree Traversal Types
When we work with Trees, we'd want to be able to explore/visit their nodes. And we'd want to do that in a specific order. So visiting each node, once, in a predefined order, in the context of a Tree, is called Tree Traversal. The two base/main ways of traversal are Depth First Search and Breadth First Search. Imagine Depth First Search as traversing vertically (along the height of the tree) and Breadth First Search as traversing the horizontally first. It's that simple.
We will explore more about Depth First Search (DFS) and Breadth First Search (BFS) in the Graphs section (you can check them now if you are impatient). But for Trees, Depth First Search is the more common approach. And DFS has tree main and most common subtypes of traversals - Preorder, Inorder, Postorder:
Preorder
In Preorder, by definition, the root node is visited first, then we start visiting recursively the tree nodes to the left (going down, in depth). Once we have visited all nodes in the left subtree, we go to the right subtree and start from the leftmost subtrees there too.
In short: root, left, right
Inorder
Now that we understand the concept of traversals and we already understood Preorder, we can be very consise and brief in the description of Inorder. For Inorder traversal, we do - left, root and then right. And we traverse it from the bottom to the top. You can easily see the order of node visiting from the animation.
Postorder
This one is simply another variant to a conceptually similar thing - but here we do left, then right and end with the root node.
Code
The code examples also show the building of the trees from the animation so that we can traverse them like in the animations.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def preorder_traversal(node):
if node is None:
return
print(node.value, end=' ')
preorder_traversal(node.left)
preorder_traversal(node.right)
def inorder_traversal(node):
if node is None:
return
inorder_traversal(node.left)
print(node.value, end=' ')
inorder_traversal(node.right)
def postorder_traversal(node):
if node is None:
return
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.value, end=' ')
# Create the tree (same as before)
root = TreeNode('A')
root.left = TreeNode('B')
root.right = TreeNode('C')
root.left.left = TreeNode('D')
root.left.right = TreeNode('E')
root.right.left = TreeNode('F')
root.right.right = TreeNode('G')
root.left.left.left = TreeNode('H')
root.left.left.right = TreeNode('I')
root.right.left.left = TreeNode('J')
root.right.left.right = TreeNode('K')
root.right.right.left = TreeNode('L')
# Perform traversals
print("Preorder Traversal: ", end='')
preorder_traversal(root)
print("\nInorder Traversal: ", end='')
inorder_traversal(root)
print("\nPostorder Traversal: ", end='')
postorder_traversal(root)
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function preorderTraversal(node) {
if (node === null) {
return;
}
console.log(node.value);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
function inorderTraversal(node) {
if (node === null) {
return;
}
inorderTraversal(node.left);
console.log(node.value);
inorderTraversal(node.right);
}
function postorderTraversal(node) {
if (node === null) {
return;
}
postorderTraversal(node.left);
postorderTraversal(node.right);
console.log(node.value);
}
// Create the tree (same as before)
let root = new TreeNode('A');
root.left = new TreeNode('B');
root.right = new TreeNode('C');
root.left.left = new TreeNode('D');
root.left.right = new TreeNode('E');
root.right.left = new TreeNode('F');
root.right.right = new TreeNode('G');
root.left.left.left = new TreeNode('H');
root.left.left.right = new TreeNode('I');
root.right.left.left = new TreeNode('J');
root.right.left.right = new TreeNode('K');
root.right.right.left = new TreeNode('L');
// Perform traversals
console.log("Preorder Traversal:");
preorderTraversal(root);
console.log("Inorder Traversal:");
inorderTraversal(root);
console.log("Postorder Traversal:");
postorderTraversal(root);
class TreeNode {
char value;
TreeNode left, right;
public TreeNode(char value) {
this.value = value;
this.left = this.right = null;
}
}
public class TreeTraversals {
public static void preorderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.value + " ");
preorderTraversal(node.left);
preorderTraversal(node.right);
}
public static void inorderTraversal(TreeNode node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
System.out.print(node.value + " ");
inorderTraversal(node.right);
}
public static void postorderTraversal(TreeNode node) {
if (node == null) {
return;
}
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.print(node.value + " ");
}
public static void main(String[] args) {
TreeNode root = new TreeNode('A');
root.left = new TreeNode('B');
root.right = new TreeNode('C');
root.left.left = new TreeNode('D');
root.left.right = new TreeNode('E');
root.right.left = new TreeNode('F');
root.right.right = new TreeNode('G');
root.left.left.left = new TreeNode('H');
root.left.left.right = new TreeNode('I');
root.right.left.left = new TreeNode('J');
root.right.left.right = new TreeNode('K');
root.right.right.left = new TreeNode('L');
System.out.print("Preorder Traversal: ");
preorderTraversal(root);
System.out.print("\nInorder Traversal: ");
inorderTraversal(root);
System.out.print("\nPostorder Traversal: ");
postorderTraversal(root);
}
}
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
char value;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(char value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
void preorderTraversal(struct TreeNode* node) {
if (node == NULL) {
return;
}
printf("%c ", node->value);
preorderTraversal(node->left);
preorderTraversal(node->right);
}
void inorderTraversal(struct TreeNode* node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left);
printf("%c ", node->value);
inorderTraversal(node->right);
}
void postorderTraversal(struct TreeNode* node) {
if (node == NULL) {
return;
}
postorderTraversal(node->left);
postorderTraversal(node->right);
printf("%c ", node->value);
}
int main() {
struct TreeNode* root = createNode('A');
root->left = createNode('B');
root->right = createNode('C');
root->left->left = createNode('D');
root->left->right = createNode('E');
root->right->left = createNode('F');
root->right->right = createNode('G');
root->left->left->left = createNode('H');
root->left->left->right = createNode('I');
root->right->left->left = createNode('J');
root->right->left->right = createNode('K');
root->right->right->left = createNode('L');
printf("Preorder Traversal: ");
preorderTraversal(root);
printf("\nInorder Traversal: ");
inorderTraversal(root);
printf("\nPostorder Traversal: ");
postorderTraversal(root);
return 0;
}
<?php
class TreeNode {
public $value;
public $left;
public $right;
public function __construct($value) {
$this->value = $value;
$this->left = null;
$this->right = null;
}
}
function preorderTraversal($node) {
if ($node === null) {
return;
}
echo $node->value . " ";
preorderTraversal($node->left);
preorderTraversal($node->right);
}
function inorderTraversal($node) {
if ($node === null) {
return;
}
inorderTraversal($node->left);
echo $node->value . " ";
inorderTraversal($node->right);
}
function postorderTraversal($node) {
if ($node === null) {
return;
}
postorderTraversal($node->left);
postorderTraversal($node->right);
echo $node->value . " ";
}
// Create the tree (same as before)
$root = new TreeNode('A');
$root->left = new TreeNode('B');
$root->right = new TreeNode('C');
$root->left->left = new TreeNode('D');
$root->left->right = new TreeNode('E');
$root->right->left = new TreeNode('F');
$root->right->right = new TreeNode('G');
$root->left->left->left = new TreeNode('H');
$root->left->left->right = new TreeNode('I');
$root->right->left->left = new TreeNode('J');
$root->right->left->right = new TreeNode('K');
$root->right->right->left = new TreeNode('L');
// Perform traversals
echo "Preorder Traversal: ";
preorderTraversal($root);
echo "\nInorder Traversal: ";
inorderTraversal($root);
echo "\nPostorder Traversal: ";
postorderTraversal($root);
?>