Hello to one and all,
Today I leant about binary tree traversal. First of all let me quickly tell you what is binary tree.
Binary tree is a tree data structure in which each node has at most two child nodes i.e. left child node and right child node.
For more about binary tree read this wiki.
And one more thing, for those who don't know what is traversal.
Traversal of tree is the process of visiting each node of the tree data structure exactly once in some systematic way.
Ok. So consider following binary tree for tree traversal explanation.
(1) Pre-order Traversal:
Pre-order traversal is followed by this process: (a) Visit the root of the tree, (b) visit the left sub tree of the root, (c) visit the right sub tree of the root.
Follow this process and you'll be having pre-order traversal as a result. Here we are dividing left node and right node of the root as sub trees. Then again we will follow the process of dividing until we reach leaf node of the sub tree.
Pre-order of given tree is: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
(2) In-order Traversal:
In-order traversal is followed by this process: (a) Visit the left sub tree of the root, (b) visit the root of the binary tree, (c) visit the right sub tree of the root.
When you visit left sub tree of the root, in our case of the binary tree, 1 will become root for the sub tree and the above process will be repeated until we reach leaf node in the sub-sequent sub trees.
In-order Traversal of given tree is: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(3) Post-order Traversal:
Post-order traversal is followed by this process: (a) Visit the left sub tree of the root node, (b) Visit the right sub tree of the root node, (c) Visit the root of the binary tree.
Post-order traversal of given tree is: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
Please correct me if I am wrong somewhere. Hope it helps.
I have read this article on This Website.
Keep learning. Keep Sharing. Keep Improving.
.....Next Time..:)
Today I leant about binary tree traversal. First of all let me quickly tell you what is binary tree.
Binary tree is a tree data structure in which each node has at most two child nodes i.e. left child node and right child node.
For more about binary tree read this wiki.
And one more thing, for those who don't know what is traversal.
Traversal of tree is the process of visiting each node of the tree data structure exactly once in some systematic way.
Ok. So consider following binary tree for tree traversal explanation.
 |
| Binary Tree |
(1) Pre-order Traversal:
Pre-order traversal is followed by this process: (a) Visit the root of the tree, (b) visit the left sub tree of the root, (c) visit the right sub tree of the root.
Follow this process and you'll be having pre-order traversal as a result. Here we are dividing left node and right node of the root as sub trees. Then again we will follow the process of dividing until we reach leaf node of the sub tree.
Pre-order of given tree is: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
(2) In-order Traversal:
In-order traversal is followed by this process: (a) Visit the left sub tree of the root, (b) visit the root of the binary tree, (c) visit the right sub tree of the root.
When you visit left sub tree of the root, in our case of the binary tree, 1 will become root for the sub tree and the above process will be repeated until we reach leaf node in the sub-sequent sub trees.
In-order Traversal of given tree is: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(3) Post-order Traversal:
Post-order traversal is followed by this process: (a) Visit the left sub tree of the root node, (b) Visit the right sub tree of the root node, (c) Visit the root of the binary tree.
Post-order traversal of given tree is: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
Please correct me if I am wrong somewhere. Hope it helps.
I have read this article on This Website.
Keep learning. Keep Sharing. Keep Improving.
.....Next Time..:)
0 comments:
Post a Comment