How to construct a binary tree from just the level order traversal string

Question

Consider a binary tree with the following properties:

1. An internal node (non-leaf node) has a value 1 if it has two children.
2. A leaf node has a value 0 since it has no children.

A level order traversal on the tree would generate a string of 1s and 0s (by printing the weird value at each node as they are visited). Now given this string construct the binary tree and perform a post order traversal on the tree. The post order string should be the output of the program.

For example: Input String is 111001000. Create a binary tree from this. Then perform the post order traversal on the tree which would result in an output: 001001011

The "crux" of the problem is to create the binary tree from just the level order string. How would I do this?

Answer 1

Taking your example of level order traversal - 111001000 The tree would be as follows

      A
    /   \ 
   B     C
  /\     /\
 D  E   F  G
       /\
      H  I

The logic is as follows.

1) Take first bit if its 1 (root) - then next 2^1 are values of children of that parent. So 2nd and 3rd bits are childern of A (root).

2) Go to next bit (1 for B) as its value is also 1 it also has 2 children and then next bit (1 for C) which also has 2 children. Second level is over and as we have 2 1's so 2^2 next bits are for level 3.

3) 111 001000 so this we have traversed and next 4 bits are children on 3rd level. 4th and 5th bits being 0 (D and E are leaf nodes and have no children - These will be children of B) and then F has bit value of 1 so 1110010 00 (bold figures) will be children of F. 7th bit is 0 and so G will also be leaf node.

4) Again loop through or try recusion - From 4th,5th and 6th and 7th bits only one bit is 1 so next 2^1 bits will be in next level and those will be children of F.

Once the tree is made then converting to PostFix is easy.

Answer 2

One possible solution (in less than an hour):

import java.util.ArrayList;
import java.util.List;

public class Main {

    private static class Node {
        private Node left;
        private Node right;
    }

    private static Node buildTree(String input) {
        char chars[] = input.toCharArray();
        if (chars.length == 0) {
            return null;
        } else {
            Node root = new Node();
            List<Node> nodeList = new ArrayList<Node>();
            nodeList.add(root);
            int pos = 0;
            while (!nodeList.isEmpty()) {
                List<Node> nextList = new ArrayList<Node>();
                for (Node n: nodeList) {
                    if (pos >= chars.length) {
                        throw new RuntimeException("Invalid input string");
                    }
                    char c = chars[pos++];
                    if (c == '1') {
                        n.left = new Node();
                        n.right = new Node();
                        nextList.add(n.left);
                        nextList.add(n.right);
                    } else if (c != '0') {
                        throw new RuntimeException("Invalid input string");
                    }
                }
                nodeList = nextList;
            }
            return root;
        }
    }

    private static String postTraverse(Node n) {
        if (n == null) {
            return "";
        } else if (n.left == null && n.right == null) {
            return "0";
        } else {
            return postTraverse(n.left) + postTraverse(n.right) + "1";
        }
    }

    public static void main(String[] args) {
        Node tree = buildTree(args[0]);
        System.out.println(postTraverse(tree));
    }
}