How do I create a tree out of this?

Question

I have a text file which has content like this:

a.b.c.d
a.c
a.d
a.x.y.z
a.x.y.a
a.x.y.b
a.subtree

I want to make this into a tree:

                        a
                  /  /    \  \   \
                 b   c     d   x  subtree
                 |              |
                 c              y   
                 |            / | \
                 d            z a  b    

Edit: The a.x.y.a path with the two a nodes need to be treated as seperate entities. Essentially the a.x.y.a is the path.

We can look at the input file like this:

Level0.Level1.Level2...

I'm trying to do this in python (I'm familiar with java too, would like java answers as well) but somehow I'm logically not able to do it.

My basic tree structure is kind of like this:

 class Tree:
     def __init__(self,data):
         self.x = data
         self.children = []

Logic is somewhat like this:

for line in open("file","r"):
    foos = line.split(".")
    for foo in foos:
        put_foo_in_tree_where_it_belongs()

How exactly do I approach this?

Also, if there is any java library for helping me do this, I can shift to java as well. Just need to accomplish this.

Answer 1

This can be easily solved using a Trie Data Structure

Following is the implementation of the Trie Data Structure using Java

import java.util.*;
class Tree
{
    class Node
    {
        String data;
        ArrayList<Node> children;

        public Node(String data)
        {
            this.data = data;
            children = new ArrayList<Node>();
        }

        public Node getChild(String data)
        {
            for(Node n : children)
                if(n.data.equals(data))
                    return n;

            return null;
        }
    }

    private Node root;

    public Tree()
    {
        root = new Node("");
    }

    public boolean isEmpty()
    {
        return root==null;
    }

    public void add(String str)
    {
        Node current = root;
        StringTokenizer s = new StringTokenizer(str, ".");
        while(s.hasMoreElements())
        {
            str = (String)s.nextElement();
            Node child = current.getChild(str);
            if(child==null)
            {
                current.children.add(new Node(str));
                child = current.getChild(str);
            }
            current = child;
        }
    }

    public void print()
    {
        print(this.root);
    }

    private void print(Node n)
    {
        if(n==null)
            return;
        for(Node c : n.children)
        {
            System.out.print(c.data + " ");
            print(c);
        }
    }
}

To verify the implementation use the below class

import java.io.*;
public class TestTree
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Tree t = new Tree();
        String s;
        int i=7;
        while(i-->0)
        {
            s = br.readLine();
            t.add(s);
        }
        System.out.println("Tree constructed!");
        t.print();
    }
}

Algorithm for add Method
1. It takes the string as input.
2. It splits the string at period (.)
3. For each substring obtained (after splitting), the value is checked, if that string is already present in the tree then it follows that path else it will insert a new string (new node) in the current level

The code will work well for input

a.b.c.d
b.c.d.e
a.e.f.a
c.d.f.c
etc

It means the first level can have any string

NOTE:
In the TestTree.java I have set i=7 just for testing purpose
You can supply your 7 input test cases

a.b.c.d
a.c
a.d
a.x.y.z
a.x.y.a
a.x.y.b
a.subtree

Print method prints the data of the Tree using preorder traversal. It is just for verification purpose you may tweak it as per your need.

Hope this helps! :)

Answer 2

Here's a Java version (untested). Note that this is complete. It doesn't require any initial transformation of the input strings. It also preserves the insertion order of the nodes of the tree:

public class Node implements Iterable<Node> {
    private String name;
    private Map<String, Node> children = new LinkedHashMap<String, Node>();

    public Node(String name) {
        this.name = name;
    }

    public String getName() { return this.name; }

    public Iterator<Node> iterator() { return children.values().iterator(); }

    private Node lookupOrAddChild(String name) {
        Node child = children.get(name);
        if (child = null) {
            child = new Node(name);
            children.put(name, child);
        }
        return child;
    }

    private void addLine(String line) {
        int pos = line.indexOf(".");
        if (pos < 0) {
            lookupOrAddChild(line);
        } else {
            node = lookupOrAddChild(line.subString(0, pos));
            node.addLine(line.substring(pos + 1));
        }
    }

    public static Node buildTree(String[] input) {
        Node node = new Node("");
        for (String line : input) {
           node.addLine(line);
        }
        // This assumes the input forms exactly one "tree"
        return node.children.values().iterator().next();
    }

Answer 3

Just for the "would like java answers as well" , i provided a Java solution :) To use, parse your inputs, push them into a queue an call insertFromRoot(Queue)

public class CustomTree {

    private TreeNode root;

    public class TreeNode {
        String                value;
        Map<String, TreeNode> children = new HashMap<String, TreeNode>();

        public TreeNode(String val) {
            this.value = val;
        }
    }

    public void insertFromRoot(Queue<String> strings) {
        if (strings != null && !strings.isEmpty()) {
            if (root == null) {
                root = new TreeNode(strings.poll());
            } else {
                if (!root.value.equals(strings.poll())) {
                    throw new InvalidParameterException("The input doesnt belong to the same tree as the root elements are not the same!");
                }
            }
        }

        TreeNode current = root;
        while (!strings.isEmpty()) {
            TreeNode newNode = null;
            if (current.children.containsKey(strings.peek())) {
                newNode = current.children.get(strings.poll());
            } else {
                newNode = new TreeNode(strings.poll());
                current.children.put(newNode.value, newNode);
            }
            current = newNode;
        }

    }
}

Edit:

Simple Usage:

public static void main(String[] args) {
        Queue<String> que = new LinkedList<String>();
        que.add("a");
        que.add("b");
        que.add("c");

        Queue<String> que2 = new LinkedList<String>();
        que2.add("a");
        que2.add("b");
        que2.add("d");

        CustomTree tree = new CustomTree();
        tree.insertFromRoot(que);
        tree.insertFromRoot(que2);
    }

Answer 4

the basic algorithm should be something like this:

def add_path(root, path):
    if path:
        child = root.setdefault(path[0], {})
        add_path(child, path[1:])

root = {}
with open('tree.txt') as f:
    for p in f:
        add_path(root, p.strip().split('.'))

import json
print json.dumps(root,  indent=4)

output:

{
    "a": {
        "x": {
            "y": {
                "a": {}, 
                "z": {}, 
                "b": {}
            }
        }, 
        "c": {}, 
        "b": {
            "c": {
                "d": {}
            }
        }, 
        "d": {}, 
        "subtree": {}
    }
}

Answer 5

I think I'd do this:

class Node(object):
    def __init__(self,data=None):
        self.children = []
        self.data = data

    def add_from_dot_str(self,s):
        elems = s.split('.')
        if self.data is None:
            self.data = elems[0]
        elif self.data != elems[0]:
            raise ValueError
        current = self
        for elem in elems[1:]:
            n = Node(elem)
            current.children.append(n)
            current = n

    @classmethod
    def from_dot_file(cls,fname):
        with open(fname) as fin:
            root = Node()
            for line in fin:
                root.add_from_dot_str(line.strip())

        return root

    def __str__(self):
        s = self.data
        s += ','.join(str(child) for child in self.children)
        return s

print Node.from_dot_file('myfilename')