How can I create a recursive binary tree with a bit sequence given by a given preorder traversal?

Before reaching 50 reputation I am putting this declaimer in the first line of my answers:

I want to make a brief response in comment instead, but I don't have enough reputation so I am making a full answer, hopefully my ill-formed answers would still help.

DFS is perfect for this task -- That's basically what pre-order traversal is doing:

def DFS(node):
    if(node == NULL) return
    sequence += notNull(node.l)
    sequence += notNull(node.r)
    DFS(node.l)
    DFS(node.r)

^^^ This is how your sequence is constructed.

Fortunately the inverse is quite straight forward:

def inverseDFS(node):
    if(node == NULL) return
    node.l = new Node() if(readBuffer(sequence) == '1') else NULL
    node.r = new Node() if(readBuffer(sequence) == '1') else NULL
    inverseDFS(node.l)
    inverseDFS(node.r)

^^^ Only line 2 and 3 is modified, now instead of determining the next character of the sequence by the existance of child, we can determine the existance of child based on the next character read, as this is an iff relationship.

Here is a more sophisicated C++ code, and yes, I know my coding style may disgust some others.

/* Author haleyk10198 */
/* FOR ACM-ICPC WF*/
#include <bits/stdc++.h>

using namespace std;

struct Node{
    static int nodeCnt;
    int id;
    Node *l, *r;
    Node(){
        l = r = nullptr;
        this->id = nodeCnt++;
    }
    friend ostream& operator<<(ostream&, const Node);
}*root = new Node();

ostream& operator<<(ostream &out, const Node node){
    cout << "Node id: " << node.id
          << " | left child is " << (node.l? node.l->id: -1)
          << " | right child is " << (node.r? node.r->id: -1) << endl;
}

int Node::nodeCnt, strStreamPos = 0;
string str;

void dfs(Node *node){
    if(not node)
        return;

    if(str[strStreamPos++] == '1')
        node->l = new Node();
    if(str[strStreamPos++] == '1')
        node->r = new Node();

    cout << *node << endl;

    dfs(node->l);
    dfs(node->r);   
}

int main(){

    cin >> str;

    dfs(root);

    return 0;
}

Your question looks likes this one: http://www.geeksforgeeks.org/construct-a-special-tree-from-given-preorder-traversal/

I modified the given code a little to meet the specific requirements of your case. I neglected the given order of nodes (letters) in your question and just focused on the structure of the tree. The time complexity is O(N) as expected. Everything seems clear so I did not give further information. If you have any question, don't hesitate to leave comment.

public class BinaryTree {
    class Node {
        char data;
        Node left, right;

        Node(char item) {
            data = item;
            left = right = null;
        }
    }

    class Index {
        int index = 0;
    }

    Node root;
    Index i = new Index();

    Node constructTreeUtil(String bitSequence, Index index_ptr, int n, Node temp) {
        int index = index_ptr.index; 

        String bits = bitSequence.substring(index * 2, index * 2 + 2);

        if (index == n)
            return null;

        temp = new Node((char) (index + 65));
        (index_ptr.index)++;

        if (bits.charAt(0) == '1')
            temp.left = constructTreeUtil(bitSequence, index_ptr, n, temp.left);

        if (bits.charAt(1) == '1')
            temp.right = constructTreeUtil(bitSequence, index_ptr, n, temp.right);

        return temp;
    }

    Node constructTree(String bitSequence, int n, Node node) {
        int index = 0;
        return constructTreeUtil(bitSequence, i, n, node);
    }

    public static void inorder(Node node) {
        if (node == null) return;
        System.out.println(node.data + "=> ");

        if (node.left != null)
          System.out.println("Left node: " + node.left.data);

        if (node.right != null)
          System.out.println("Right node: " + node.right.data);

        System.out.println();
        inorder(node.left);
        inorder(node.right);
    }

    public static void main(String args[]) {
        BinaryTree tree = new BinaryTree();

        // Bit sequence
        String bitSequence = "11010011001000";

        // Number of nodes
        int n = bitSequence.length() / 2;

        // Tree construction
        Node node = tree.constructTree(bitSequence, n, tree.root);

        // Print tree nodes inorder
        inorder(node);
    }
}