Traversal in Binary Tree
- Traversal meant visiting every node in the list at least once.
- Traversal has several applications
- To just visit each node and print their value.
- To add each of those elements
- We have three different ways to traverse in binary tree.
- Inorder
- PostOrder
- PreOrder
Let's understand each of them
PreOrder Traversal
ROOT → LEFT NODE → RIGHT NODE
- First node we start with is the root node.
- And thereafter you visit the left.
- And then the right subtree
- First visit section 1, then 2, and then 3.
- As seen in above example
- Fist visit the the root node element 7
- And then move to the left subtree.
- The left subtree in itself is a tree with root node 11
- So, you visit that and move further to the left subtree of this subtree
- There you see single element 7, you visit that
- and then move to the right subtree which is a NULL
- So, you're finished with the left subtree of the main tree.
- Now you move to the right subtree which has element 2 as its node.
- And then a NULL to its left and elements 9 to its right.
- So basically, you recursively visit each subtree in the same order.
- And you final traversal order is:
PostOrder Travesal
LEFT NODE → RIGHT NODE → ROOT NODE
- In this traversal technique, things are quite opposite to the PreOrder traversal
- Here, you first visit the left subtreeli
- and then the right subtree.
- So, the last node you'll visit is the root node
- First visit section 1, then 2 and then 3.
-
General Idea
- Each time you get a tree, you first visit its left subtree
- and then its right subtree
- and then move to its root node
Final traversal order should be.
InOrder Traversal
LEFT NODE → ROOT NODE → RIGHT NODE
- Start with the left subtree
- Then go to the root node
- And then visit the right subtree.
- First visit section 1, then 2, and then 3.
Traversal on above example looks like this ↓ 