The tree is a non-linear data structure, unlike Linked List and Arrays. It is a hierarchical data structure that can be traversed in the following ways:-
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level Order Traversal.
For the given Tree,
Inorder Traversal
Inorder Traversal is one of the tree traversals in which the left subtree is visited first then visit the root and then the right subtree is visited.
Inorder Traversal – 4 2 5 1 6 3
Algorithm of Inorder Traversal
- Traverse the left subtree
- Print the root
- Traverse the right subtree
Implementation of Inorder Traversal
C++
struct node {
int data;
struct node * left, * right;
};
void inOrderTrav(node * curr, vector < int > & inOrder) {
if (curr == NULL)
return;
inOrderTrav(curr -> left, inOrder);
inOrder.push_back(curr -> data);
inOrderTrav(curr -> right, inOrder);
}
Java
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class TUF {
static void inOrderTrav(Node curr, ArrayList < Integer > inOrder) {
if (curr == null)
return;
inOrderTrav(curr.left, inOrder);
inOrder.add(curr.data);
inOrderTrav(curr.right, inOrder);
}
}
Read Inorder Traversal in details.
Applications of Inorder Traversal
- If inorder traversal of Binary Search Tree (BST) is done , we get increasing order.
- We can get reversed order / Decreasing order by doing inorder traversal in reverse order ( where right subtree is called first and then left subtree is called)
Preorder Traversal
Preorder Traversal is one of the tree traversals in which root is visited then the left subtree is visited and then the right subtree is visited.
Preorder Traversal – 1 2 4 5 3 6
Algorithm of Preorder Traversal
- Print the root
- Traverse the left subtree
- Traverse the right subtree
Implementation of Preorder Traversal
C++
struct node {
int data;
struct node * left, * right;
};
void preOrderTrav(node * curr, vector < int > & preOrder) {
if (curr == NULL)
return;
preOrder.push_back(curr -> data);
preOrderTrav(curr -> left, preOrder);
preOrderTrav(curr -> right, preOrder);
}
Java
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
Node() {
}
}
public class TUF {
static void preOrderTrav(Node curr, ArrayList < Integer > preOrder) {
if (curr == null)
return;
preOrder.add(curr.data);
preOrderTrav(curr.left, preOrder);
preOrderTrav(curr.right, preOrder);
}
}
Read Preorder Traversal in details
Applications of Preorder Traversal
- The main use of Preorder is to get copy of Tree.
- Other use is to generate Prefix expression.
Postorder Traversal
Postorder Traversal is one of the tree traversals in which the left subtree is visited, then the right subtree is visited, and then the root is visited.
Postorder Traversal – 4 5 2 6 3 1
Algorithm of Postorder Traversal
- Traverse the left subtree
- Traverse the right subtree
- Print the root
Implementation of Postorder Traversal
C++
struct node {
int data;
struct node * left, * right;
};
void postOrderTrav(node * curr, vector < int > & postOrder) {
if (curr == NULL)
return;
postOrderTrav(curr -> left, postOrder);
postOrderTrav(curr -> right, postOrder);
postOrder.push_back(curr -> data);
}
Java
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
public class TUF {
static void postOrderTrav(Node curr, ArrayList < Integer > postOrder) {
if (curr == null)
return;
postOrderTrav(curr.left, postOrder);
postOrderTrav(curr.right, postOrder);
postOrder.add(curr.data);
}
}
Read Postorder Traversal in details.
Applications of Postorder Traversal
- The main use of Postorder is to delete the tree ( Before deleting the parent, we should delete children first ).
- Other use is to generate Postfix expression.
Levelorder Traversal
Level order Traversal is one of the tree traversals in which every node in the tree is visited level by level.
Level Order Traversal – 1 2 3 4 5 6
Algorithm of Levelorder Traversal
- Remove a node from queue.
- Print the node.
- Add all of its children in the queue
Implementation of Levelorder Traversal
C++
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(root == NULL) return ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> level;
for(int i = 0;i<size;i++) {
TreeNode *node = q.front();
q.pop();
if(node->left != NULL) q.push(node->left);
if(node->right != NULL) q.push(node->right);
level.push_back(node->val);
}
ans.push_back(level);
}
return ans;
}
Java
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(subList);
}
return wrapList;
}
Read LevelOrder Traversal in details
Applications of Level order Traversal
- Level order traversal is actually Breadth First Search.
- Finding connected components in graph data structure.
Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article