Menu
What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion?
394
PostOrder Traversal without Recursion is a traversal method, where the left subtree is visited first, then right sub tree, and finally root node. Unlike array and linked lists, being linear data structures, we have several ways of traversing binary tree due to its hierarchical nature.
Solution: Morris Traversal Morris Traversal is a method based on the idea of a threaded binary tree and can be used to traverse a tree without using recursion or stack.
The idea is to move down to leftmost node using left pointer. While moving down, push root and root's right child to stack. Once we reach leftmost node, print it if it doesn't have a right child. If it has a right child, then change root so that the right child is processed before.
The postorder traversal is one of the traversing techniques used for visiting the node in the tree. It follows the principle LRN (Left-right-node). Postorder traversal is used to get the postfix expression of a tree. Traverse the left subtree by calling the postorder function recursively.
Here's the version with one stack and without a visited flag:
private void postorder(Node head) { if (head == null) { return; } LinkedList<Node> stack = new LinkedList<Node>(); stack.push(head); while (!stack.isEmpty()) { Node next = stack.peek(); boolean finishedSubtrees = (next.right == head || next.left == head); boolean isLeaf = (next.left == null && next.right == null); if (finishedSubtrees || isLeaf) { stack.pop(); System.out.println(next.value); head = next; } else { if (next.right != null) { stack.push(next.right); } if (next.left != null) { stack.push(next.left); } } } } If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
