/**
 * output:
 * Post order Traversal: [1, 4, 7, 6, 3, 13, 14, 10, 8]
 * Post order Traversal: [2, 3, 1]
 * Post order Traversal: [3, 4, 2, 1]
 * /
import java.util.*;

public class BTree {
    
    Node root;
    
    class Node {
        Node left;
        Node right;
        String val;
        Node(String val) {
            this.val = val;
        }
    }
    
    public static void main(String[] args) {
        String[] nodes = {"8", "3", "10", "1", "6", "#", "14", "#", "#", "4", "7", "13"};
        BTree btree = new BTree();
        btree.makeTree(nodes);
        ArrayList<String> result = new ArrayList();
        btree.postOrder(btree.root, result);
        System.out.println("Post order Traversal: "+Arrays.toString(result.toArray()));
        
        // Example - 1
        String[] nodes2 = {"1", "2", "3"};
        btree.makeTree(nodes2);
        ArrayList<String> result2= new ArrayList();
        btree.postOrder(btree.root, result2);
        System.out.println("Post order Traversal: "+Arrays.toString(result2.toArray()));
        
        // Example - 2
        String[] nodes3 = {"1", "2", "#", "3", "4"};
        btree.makeTree(nodes3);
        ArrayList<String> result3= new ArrayList();
        btree.postOrder(btree.root, result3);
        System.out.println("Post order Traversal: "+Arrays.toString(result3.toArray()));
    }
    
    private void makeTree(String[] nodes) {
        root = new Node(nodes[0]);
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        int pointer = 1;
        for (int i = 1; i < nodes.length && !q.isEmpty(); i = i+2) {
            Node curr = q.remove();
            if (nodes[i] == "#") {
                curr.left = null;
            } else {
                Node left = new Node(nodes[i]);
                curr.left = left;
                q.add(left);
            }
            if (i+1 < nodes.length) {
                if (nodes[i+1] == "#") {
                    curr.right = null;
                } else {
                    Node right = new Node(nodes[i+1]);
                    q.add(right);
                    curr.right = right;
                }
            }
        }
    }
    
    private void postOrder(Node root, ArrayList result) {
        if (root == null) {
            return;
        } else if (root.left == null && root.right == null) {
            result.add(root.val);
            return;
        }
        postOrder(root.left, result);
        postOrder(root.right, result);
        result.add(root.val);
    }
}