Saturday, 8 October 2016

Post Order binary tree traversal in Java - Recursion and Iteration

This is the third article on tree traversal. In the last couple of articles, I have shown you how to implement preorder and inorder traversal in Java, both recursively and iteratively and today, you will learn about the post order traversal. Out of these three main tree traversal algorithms, the post-order traversal is most difficult to implement, especially the iterative version. In post order traversal, you first visit left subtree, then right subtree and at last you print the value of root or not. So, the value of root is always printed at last in the post-order traversal. As I told you before, all three preOrder, inOrder, and postOrder are depth-first algorithms so they go down in the binary tree first before visiting nodes of the same level. The implementation of the recursive algorithm is very simple, you just need to adjust the order of recursive call according to the algorithm and you are done, but iterative algorithm requires some effort to get it right, which you will see in this article.
Read more »

No comments:

Post a Comment