A tree is a nonlinear data structure that is a collection of entities called nodes. Edges connect nodes. Each node contains a value, and it may or may not have a child node.
Unlike other linear data structures such as arrays, linked list, stack, and queue that store data sequentially, trees organize data hierarchically.
While performing any operation in a linear data structure, the time complexity increases with the increase in the data size.
Tree data structures allow better accessibility to the data as it is a non-linear data structure.
Traversing a tree is the process of visiting every node in the tree. Since all nodes are connected via edges, traversal is always started from the root node.
It is not possible to randomly access a node in a tree.
Every tree is a consists of :
struct node
{
int data;
struct node* left; // left child
struct node* right; // right child
}
Note : The struct node pointed to by left and right might have other left and right children and should be considered as sub-trees instead of sub-nodes.
A hierarchical data structure like a tree can be traversed in three ways :
In inorder traversal, the output will produce sorted key values in ascending order.
Until all nodes are traversed :
Note : Every node may represent a subtree itself.
Start from 3, then move to its left subtree 5. 5 is also traversed in-order.
The process goes on until all the nodes are visited.
The output of inorder traversal of this tree will be :
11 → 5 → 8 → 3 → 9 → 6 → 1
void inorder(struct Node* node)
{
if (node != NULL)
{
inorder(node->left);
print(node->data);
inorder(node->right);
}
}
Note : Every node may represent a subtree itself.
Start from 3, then first visit 3 itself and then move to its left subtree 5. 5 is also traversed pre-order.
The process goes on until all the nodes are visited.
The output of pre-order traversal of this tree will be :
3→ 5 → 11 → 8 → 6 → 9 → 1
void preorder(struct Node* node)
{
if (node != NULL)
{
print(node->data);
preorder(node->left);
preorder(node->right);
}
}
Until all nodes are traversed :
Note : Every node may represent a subtree itself.
Start from 3,then traverse the left subtree 5. 5 is also traversed post-order.
The process goes on until all the nodes are visited.
The output of post-order traversal of this tree will be :
11 → 8 → 5 → 9 → 1 → 6 → 3
void postorder(struct Node* node)
{
if (node != NULL)
{
postorder(node->left);
postorder(node->right);
print(node->data);
}
}