Tree: Postorder Traversal Hackerrank Solution

Complete the postOrder function in your editor below, which has  parameter: a pointer to the root of a binary tree. It must print the values in the tree’s postorder traversal as a single line of space-separated values.

Input Format

Our hidden tester code passes the root node of a binary tree to your postOrder function.

Constraints

1 <= Nodes in the tree <= 500

Output Format

Print the tree’s postorder traversal as a single line of space-separated values.

Sample Input

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

Sample Output

4 3 6 5 2 1 

Algorithm:

1.We will use two stack method to find postorder.
Create two stacks s1, s2.
2.Push the root element in stack s1.
3.Loop while stack s1 is not empty.
4.Pop the stack top s1 and collect it temp node
5.After that push the popped node in s2.
6.Now iterate through left and right sub tree and push it to the stack s1.
7.After the stack s1 is empty print the elements of stack s2.

Iterative apporach:

package tree;

import java.util.Stack;

public class PostOrderTraversal {
	public static void postorder(Node root) {
		if(root == null)
			return;
		
		// create two stacks
		Stack<Node> s1 = new Stack<>();
		Stack<Node> s2 = new Stack<>();
		s1.push(root);
		
		while(!s1.isEmpty()) {
			
			Node curr = s1.pop();
			
			s2.push(curr);
			
			if(curr.left != null) {
				s1.push(curr.left);
			}
			if(curr.right != null) {
				s1.push(curr.right);
			}
		}
		
		while(!s2.isEmpty()) {
			Node ans = s2.pop();
			System.out.print(ans.data + " ");
		}
		
		
		
	}

	public static void main(String[] args) {
		Node root= new Node(1); 
        root.left= new Node(2); 
      root.right= new Node(3); 
      root.left.left= new Node(4); 
     root.left.right= new Node(5); 
         
       System.out.println("Inorder traversal of binary tree is "); 
       postorder(root);
		

	}

}

Recursive approach:

  public static void postOrder(Node root) {
        if(root == null)
        return;

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");

    }

Hope you all get the concept of postOrder traversal using both iterative and recursive approach.

To learn recursion and tree traversal in details .

In the next blog we will see other tree implementation using both methods i.e iterative and recursive in java.

So till then Bye Bye…!

Happy Coding..!

Thank You…!



Categories: HackerRank Questions

Tags: , , , , , ,

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: