A Tree is said to be a Binary Tree if all of its nodes have atmost 2 children. That is, all of its node can have either no child, 1 child or 2 child nodes.

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which is linear data structures and have only one logical way to traverse the elements, trees can be traversed in different ways. Following are the generally used ways for traversing trees.

The tree traversal techniques given below:

Inorder Traversal (<left><root><right>)

preorder Traversal (<root><left><right>)

Postorder Traversal (<left><right><root>)

Let’s see the example:

1.Inorder Traversal: Process all nodes of a tree by recursively processing the left subtree, then processing the root, and finally the right subtree. Also known as symmetric traversal.

Algorithm:

1. Traverse the left subtree, i.e., call Inorder(left->subtree) 2. Visit the root. 3. Traverse the right subtree, i.e., call Inorder(right->subtree)

Inorder = 4 2 5 1 6 3 7

2. Preorder Traversal: Process all nodes of a tree by processing the root, then recursively processing all subtrees. Also known as prefix traversal.

Algorithm:

1. Visit the root.
2. Traverse the left subtree, i.e.,
call Preorder(left-subtree)
3. Traverse the right subtree, i.e.,
call Preorder(right-subtree)

Preorder = 1 2 4 5 3 6 7

3. Postorder Traversal: Process all nodes of a tree by recursively processing all subtrees, then finally processing the root. Also known as postfix traversal.

Algorithm:

1. Traverse the left subtree, i.e., call Postorder(left-subtree) 2. Traverse the right subtree, i.e., call Postorder(right-subtree) 3. Visit the root.

Postorder = 4 5 2 6 7 3 1

Hope you guys understand what is binary tree and its traversing techniques.

In the next blog we will see the implementation of these techniques using both methods i.e iterative and recursive in java.

## Leave a Reply