ParsePrefixOperationsToBinaryTrees.java

// Parse prefix representation into binary tree
// +12 =>   +
//         / \
//        1   2


public class Solution {
    
    class Node {
        char c; 
        Node left, right; 
        Node(char c) {
            this.c = c; 
        }
    }
    
    private int i = 0; 
    private String s; 
    
    public Solution(String s) {
        this.s = s; 
    }
    
    public static void main(String args[] ) throws Exception {
        Solution sln = new Solution("+1+23");
        Node res = sln.helper(); 
        sln.print(res);
    }
    
    private void print(Node node) {
        Queue<Node> queue = new LinkedList(); 
        queue.add(node);
        
        while (queue.size()!=0) {
            int size = queue.size(); 
            while (size > 0) {
                Node front = queue.remove();
                System.out.print(front.c + " ");
                if (front.left != null) queue.add(front.left);
                if (front.right != null) queue.add(front.right);
                size--;     
            }
            System.out.println();
        }
    }
    
    public Node helper() {
            if (i == s.length()) return null; 
            char c = s.charAt(i); 
            i++; 
            Node node = new Node(c);
            
            if (c == '+' || c == '-') {
                Node left = helper(); 
                Node right = helper(); 
                node.left = left; 
                node.right = right; 
            } 
            
            return node; 
    }
}