Binary tree from preorder bitstring

Question

I need to build a binary tree from a preorder bitstring (which is piped into standard input in a stream) and I was wondering if my understanding of this was correct.

If I had a preorder bitstring of 11110001000 (where 1 indicates an internal node and 0 indicates an external node), would that result in a binary tree like this?

        1
       / \
      1   0
     / \
    1   1
   / \ / \
  1  00   0
 / \
0   0

After building the binary tree from the preorder bitstring (which is given through the input), I also need to find the height, path length, and whether the binary tree is complete or not. However I'm having trouble progressing to the point where I'm able to do this because I don't know how to get started on implementing the preorder bitstring -> binary tree conversion in Java. Could anyone please give hints on how I'd get started on building a binary tree from the preorder bitstring?

Answer 1

You can start from this simple program I made some time ago and adapt it to accept a binary string as input instead of the manual input:

import javax.swing.JOptionPane;

class Node {
    int info;
    Node fs;
    Node fd;
}

class BinaryTree {

    public static void main(String[] args) {

        Node tree = null;
        tree = insertRecursivePreorder(tree);

    }

    static Node insertRecursivePreorder (Node n) {
      String input = JOptionPane.showInputDialog("Insert node, 0 to end: \n");
      int dato = Integer.parseInt(input);

      if (dato == 0) {
          n=null;
      } else {
          n=new Node();
          n.info=dato;
          n.fs=insertRecursivePreorder(n.fs);
          n.fd=insertRecursivePreorder(n.fd);
      }
      return n;
    }

}

Answer 2

You can begin from here. And if you know c++, this article will be also useful.

The main idea is to have a Node class, which has references to the left and to the right nodes. Then, all you need to do, is navigate through the nodes.