Binary Tree Postorder Traversal (Java) Among preoder, inorder and postorder bina

Question

Binary Tree Postorder Traversal (Java)

Among preoder, inorder and postorder binary tree traversal problems, postorder traversal is the most complicated one.

Java Solution

The key to t iterative postorder traversal is the following:

The order of "Postorder" is: left child -> right child -> parent node.

Find the relation between the previously visited node and the current node

Use a stack to track nodes

As we go down the tree to the left, check the previously visited node. If the current node is the left or right child of the previous node, then keep going down the tree, and add left/right node to stack when applicable. When there are no children for the current node, i.e., the current node is a leaf, pop it from the stack. Then the previous node becomes the current node for next loop. Please include as many comments as possible to explain the post-order traversal algorithm.

Let me try to illustrate what I mean by writing comments to the above source code.

  //Definition for binary tree  public class TreeNode {      int val;      TreeNode left;      TreeNode right;      TreeNode(int x) { val = x; }  }        public class Solution {      public ArrayList<Integer> postorderTraversal(TreeNode root) {             ArrayList<Integer> lst = new ArrayList<Integer>();             if(root == null)              return lst;              Stack<TreeNode> stack = new Stack<TreeNode>();          stack.push(root);             TreeNode prev = null;          while(!stack.empty()){              TreeNode curr = stack.peek();                 // go down the tree.              //check if current node is leaf, if so, process it and pop stack,              //otherwise, keep going down              if(prev == null || prev.left == curr || prev.right == curr){                  //prev == null is the situation for the root node                  if(curr.left != null){                      stack.push(curr.left);                  }else if(curr.right != null){                      stack.push(curr.right);                  }else{                      stack.pop();                      lst.add(curr.val);                  }                 //go up the tree from left node                  //need to check if there is a right child              //if yes, push it to stack              //otherwise, process parent and pop stack              }else if(curr.left == prev){                  if(curr.right != null){                      stack.push(curr.right);                  }else{                      stack.pop();                      lst.add(curr.val);                  }                 //go up the tree from right node               //after coming back from right node, process parent node and pop stack.               }else if(curr.right == prev){                  stack.pop();                  lst.add(curr.val);              }                 prev = curr;          }             return lst;      }  }

Explanation / Answer

//Definition for binary tree public class TreeNode { int val; //data in the tree node TreeNode left; //pointer to left child of node TreeNode right; //pointer to right child of node TreeNode(int x) { val = x; } //constructor to initialize value of data } public class Solution { public ArrayList postorderTraversal(TreeNode root) { //returns post order traversal ArrayList lst = new ArrayList(); //create arraylist, initially empty if(root == null) //if root is empty return return lst; Stack stack = new Stack(); //create new stack stack.push(root); //push the root onto stack TreeNode prev = null; while(!stack.empty()){//while stack is not empty TreeNode curr = stack.peek(); //see object at top of stack //post oder is Left Right Root // go down the tree. //check if current node is leaf, if so, process it and pop stack, //otherwise, keep going down if(prev == null || prev.left == curr || prev.right == curr){ //prev == null is the situation for the root node if(curr.left != null){ stack.push(curr.left); //push onto stack left child }else if(curr.right != null){ stack.push(curr.right);//push right }else{ stack.pop(); //if both right and left child null, process the root lst.add(curr.val); //add it to traversal } //go up the tree from left node //need to check if there is a right child //if yes, push it to stack //otherwise, process parent and pop stack }else if(curr.left == prev){ if(curr.right != null){ stack.push(curr.right); }else{ stack.pop(); lst.add(curr.val); } //go up the tree from right node //after coming back from right node, process parent node and pop stack. }else if(curr.right == prev){ stack.pop(); lst.add(curr.val); } prev = curr; //keep track of prev ; in next iteration prev becomes curr } return lst; //return the traversal list } }

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---