Consider the tree:

To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.

Therefore, the Postorder traversal of the above tree will outputs:

0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Recursive solution

Iterative solution

Iterative solution involves 2 stacks. So if we want to do the same thing iteratively; we just need to maintain 2 stacks child and parent. Following is the algorithm of this method:

Here is the code for the same:

Lets see a light example of how it works. Suppose we have a binary tree as shown below and we need to compute its post order traversal. It's post order traversal will be

Here is how the stack grows:

Iterative solution using arrays

http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.

Therefore, the Postorder traversal of the above tree will outputs:

0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Recursive solution

postorder(Node *root) { if(root) { postorder(root->left); postorder(root->right); printf("Value : [%d]", root->value); } }

Iterative solution

Iterative solution involves 2 stacks. So if we want to do the same thing iteratively; we just need to maintain 2 stacks child and parent. Following is the algorithm of this method:

- Push the root node to the child stack.
- while child stack is not empty
- Pop a node from the child stack, and push it to the parent stack.
- Push its left child followed by its right child to the child stack.
- end while
- Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.

Here is the code for the same:

void postOrderTraversalIterativeTwoStacks(TreeNode *root) { if (!root) return; stack<binarytree*> child; stack<binarytree*> parent; //Initialization child.push(root); while (!child.empty()) { BinaryTree *curr = child.top(); parent.push(curr); child.pop(); if (curr->left) child.push(curr->left); if (curr->right) child.push(curr->right); } //Printing the post order traversal while (!parent.empty()) { cout << parent.top()->data << " "; parent.pop(); } }

**Dry running the code**Lets see a light example of how it works. Suppose we have a binary tree as shown below and we need to compute its post order traversal. It's post order traversal will be

*{A, C, E, D, B, H, I, G, F}*Here is how the stack grows:

Iterative solution using arrays

void iterativePostorder(node *root) { struct { node *node; unsigned vleft :1; // Visited left? unsigned vright :1; // Visited right? }save[100]; int top = 0; save[top++].node = root; while ( top != 0 ) { /* Move to the left subtree if present and not visited */ if(root->left != NULL && !save[top].vleft) { save[top].vleft = 1; save[top++].node = root; root = root->left; continue; } /* Move to the right subtree if present and not visited */ if(root->right != NULL && !save[top].vright ) { save[top].vright = 1; save[top++].node = root; root = root->right; continue; } printf("[%d] ", root->value); /* Clean up the stack */ save[top].vleft = 0; save[top].vright = 0; /* Move up */ root = save[--top].node; } }

http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

## 0 comments:

## Post a Comment