Java tree data-structure?

By | December 14, 2017
Questions:

Is there a good available (standard Java) data structure to represent a tree in Java?

Specifically I need to represent the following:

  • The tree at any node can have an arbitrary number of children
  • Each node (after the root) is just a String (whose children are also Strings)
  • I need to be able to get all the children (some sort of list or array of Strings) given an input string representing a given node

Is there an available structure for this or do I need to create my own (if so implementation suggestions would be great).

Answers:

Here:

public class Tree<T> {
    private Node<T> root;

    public Tree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

That is a basic tree structure that can be used for String or any other object. It is fairly easy to implement simple trees to do what you need.

All you need to add are methods for add to, removing from, traversing, and constructors. The Node is the basic building block of the Tree.

Questions:
Answers:

Yet another tree structure:

public class TreeNode<T> implements Iterable<TreeNode<T>> {

    T data;
    TreeNode<T> parent;
    List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }

    // other features ...

}

Sample usage:

TreeNode<String> root = new TreeNode<String>("root");
{
    TreeNode<String> node0 = root.addChild("node0");
    TreeNode<String> node1 = root.addChild("node1");
    TreeNode<String> node2 = root.addChild("node2");
    {
        TreeNode<String> node20 = node2.addChild(null);
        TreeNode<String> node21 = node2.addChild("node21");
        {
            TreeNode<String> node210 = node20.addChild("node210");
        }
    }
}

BONUS
See fully-fledged tree with:

  • iterator
  • searching
  • Java/C#

https://github.com/gt4dev/yet-another-tree-structure

Questions:
Answers:

There is actually a pretty good tree structure implemented in the JDK.

Have a look at javax.swing.tree, TreeModel, and TreeNode. They are designed to be used with the JTreePanel but they are, in fact, a pretty good tree implementation and there is nothing stopping you from using it with out a swing interface.

Note that as of Java 9 you may wish not to use these classes as they will not be present in the ‘Compact profiles’.

Questions:
Answers:

What about this? (BTW, no matter what I seem to try, I cannot paste code that the site’s code formatter will process properly. Sorry about that.)

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author ycoppel@google.com (Yohann Coppel)
  * 
  * @param <T>
  *          Object's type in the tree.
*/
public class Tree<T> {

  private T head;

  private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>();

  private Tree<T> parent = null;

  private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>();

  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }

  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
      locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }

  public Tree<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<T>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }

  public Tree<T> setAsParent(T parentRoot) {
    Tree<T> t = new Tree<T>(parentRoot);
    t.leafs.add(this);
    this.parent = t;
    t.locate = this.locate;
    t.locate.put(head, this);
    t.locate.put(parentRoot, t);
    return t;
  }

  public T getHead() {
    return head;
  }

  public Tree<T> getTree(T element) {
    return locate.get(element);
  }

  public Tree<T> getParent() {
    return parent;
  }

  public Collection<T> getSuccessors(T root) {
    Collection<T> successors = new ArrayList<T>();
    Tree<T> tree = getTree(root);
    if (null != tree) {
      for (Tree<T> leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }

  public Collection<Tree<T>> getSubTrees() {
    return leafs;
  }

  public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) {
    for (Tree<T> tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList<T>();
  }

  @Override
  public String toString() {
    return printTree(0);
  }

  private static final int indent = 2;

  private String printTree(int increment) {
    String s = "";
    String inc = "";
    for (int i = 0; i < increment; ++i) {
      inc = inc + " ";
    }
    s = inc + head;
    for (Tree<T> child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}

Questions:
Answers:

I wrote a little library that handles generic trees. It’s much more lightweight than the swing stuff. I also have a maven project for it.

Questions:
Answers:
public class Tree {
    private List<Tree> leaves = new LinkedList<Tree>();
    private Tree parent = null;
    private String data;

    public Tree(String data, Tree parent) {
        this.data = data;
        this.parent = parent;
    }
}

Obviously you can add utility methods to add/remove children.

Questions:
Answers:

You should start by defining what a tree is (for the domain), this is best done by defining the interface first. Not all trees structures are modifyable, being able to add and remove nodes should be an optional feature, so we make an extra interface for that.

There’s no need to create node objects which hold the values, in fact I see this as a major design flaw and overhead in most tree implementations. If you look at Swing, the TreeModel is free of node classes (only DefaultTreeModel makes use of TreeNode), as they are not really needed.

public interface Tree <N extends Serializable> extends Serializable {
    public List<N> getRoots ();
    public N getParent (N node);
    public List<N> getChildren (N node);
}

public interface MutableTree <N extends Serializable> extends Tree<N> {
    public boolean add (N parent, N node);
    public boolean remove (N node, boolean cascade);
}

Given these interfaces, code that uses trees doesn’t have to care much about how the tree is implemented. This allows you to use generic implementations as well as specialized ones, where you realize the tree by delegating functions to another API.
Example: File tree structure.

public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<String>();
        tree.add("A", "B");
        tree.add("A", "C");
        tree.add("C", "D");
        tree.add("E", "A");
        System.out.println(tree);
    }

    private final Map<N, N> nodeParent = new HashMap<N, N>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();

    private void checkNotNull(N node, String parameterName) {
        if (node == null)
            throw new IllegalArgumentException(parameterName + " must not be null");
    }

    @Override
    public boolean add(N parent, N node) {
        checkNotNull(parent, "parent");
        checkNotNull(node, "node");

        // check for cycles
        N current = parent;
        do {
            if (node.equals(current)) {
                throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent");
            }
        } while ((current = getParent(current)) != null);

        boolean added = nodeList.add(node);
        nodeList.add(parent);
        nodeParent.put(node, parent);
        return added;
    }

    @Override
    public boolean remove(N node, boolean cascade) {
        checkNotNull(node, "node");

        if (!nodeList.contains(node)) {
            return false;
        }
        if (cascade) {
            for (N child : getChildren(node)) {
                remove(child, true);
            }
        } else {
            for (N child : getChildren(node)) {
                nodeParent.remove(child);
            }
        }
        nodeList.remove(node);
        return true;
    }

    @Override
    public List<N> getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return nodeParent.get(node);
    }

    @Override
    public List<N> getChildren(N node) {
        List<N> children = new LinkedList<N>();
        for (N n : nodeList) {
            N parent = nodeParent.get(n);
            if (node == null && parent == null) {
                children.add(n);
            } else if (node != null && parent != null && parent.equals(node)) {
                children.add(n);
            }
        }
        return children;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        dumpNodeStructure(builder, null, "- ");
        return builder.toString();
    }

    private void dumpNodeStructure(StringBuilder builder, N node, String prefix) {
        if (node != null) {
            builder.append(prefix);
            builder.append(node.toString());
            builder.append('\n');
            prefix = "    " + prefix;
        }
        for (N child : getChildren(node)) {
            dumpNodeStructure(builder, child, prefix);
        }
    }
}

Questions:
Answers:

No answer mentions over-simplified but working code, so here it is:

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}

Questions:
Answers:

Along the same lines as Gareth’s answer, check out DefaultMutableTreeNode. It’s not generic, but otherwise seems to fit the bill. Even though it’s in the javax.swing package, it doesn’t depend on any AWT or Swing classes. In fact, the source code actually has the comment // ISSUE: this class depends on nothing in AWT -- move to java.util?

Questions:
Answers:

You can use any XML API of Java as Document and Node..as XML is a tree structure with Strings

Questions:
Answers:

There are a couple of tree data structures in Java, such as DefaultMutableTreeNode in JDK Swing, Tree in Stanford parser package, and other toy codes. But none of these are sufficient yet small enough for general purpose.

Java-tree project attempts to provide another general-purpose tree data structure in Java. The difference between this and others are

  • Totally free. You can use it anywhere (except in your homework :P)
  • Small but general enough. I put everything of the data structure in one class file, so it would be easy to copy/paste.
  • Not just a toys. I am aware of dozens of Java tree codes that can only handle binary trees or limited operations. This TreeNode is much more than that. It provides different ways of visiting nodes, such as preorder, postorder, breadthfirst, leaves, path to root, etc. Moreover, iterators are provided too for the sufficiency.
  • More utils will be added. I am willing to add more operations to make this project comprehensive, especially if you send a request through github.
Questions:
Answers:

Since the question asks for an available data structure, a tree can be constructed from lists or arrays:

Object[] tree = new Object[2];
tree[0] = "Hello";
{
  Object[] subtree = new Object[2];
  subtree[0] = "Goodbye";
  subtree[1] = "";
  tree[1] = subtree;
}

instanceof can be used to determine whether an element is a subtree or a terminal node.

Questions:
Answers:
public abstract class Node {
  List<Node> children;

  public List<Node> getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

As simple as it gets and very easy to use. To use it, extend it:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}

Questions:
Answers:

If you’re doing whiteboard coding, an interview, or even just planning to use a tree, the verbosity of these is all a little much.

It should further be said that the reason a tree is not in there like, say, a Pair (about which the same could be said), is because you should be encapsulating your data in the class using it, and the simplest implementation looks like:

/***
/* Within the class that's using a binary tree for any reason. You could 
/* generalize with generics IFF the parent class needs different value types.
 */
private class Node {
  public String value;
  public Node[] nodes; // Or an Iterable<Node> nodes;
}

That’s really it for an arbitrary width tree.

If you wanted a binary tree it’s often easier to use with named fields:

private class Node { // Using package visibility is an option
  String value;
  Node left;
  Node right;
}

Or if you wanted a trie:

private class Node {
  String value;
  Map<char, Node> nodes;
}

Now you said you want

to be able to get all the children (some sort of list or array of Strings) given an input string representing a given node

That sounds like your homework.
But since I’m reasonably sure any deadline has now passed…

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

public class kidsOfMatchTheseDays {
 static private class Node {
   String value;
   Node[] nodes;
 }

 // Pre-order; you didn't specify.
 static public List<String> list(Node node, String find) {
   return list(node, find, new ArrayList<String>(), false);
 }

 static private ArrayList<String> list(
     Node node,
     String find,
     ArrayList<String> list,
     boolean add) {
   if (node == null) {
     return list;
   }
   if (node.value.equals(find)) {
     add = true;
   }
   if (add) {
     list.add(node.value);
   }
   if (node.nodes != null) {
     for (Node child: node.nodes) {
       list(child, find, list, add);
     }
   }
   return list;
 }

 public static final void main(String... args) {
   // Usually never have to do setup like this, so excuse the style
   // And it could be cleaner by adding a constructor like:
   //     Node(String val, Node... children) {
   //         value = val;
   //         nodes = children;
   //     }
   Node tree = new Node();
   tree.value = "root";
   Node[] n = {new Node(), new Node()};
   tree.nodes = n;
   tree.nodes[0].value = "leftish";
   tree.nodes[1].value = "rightish-leafy";
   Node[] nn = {new Node()};
   tree.nodes[0].nodes = nn;
   tree.nodes[0].nodes[0].value = "off-leftish-leaf";
   // Enough setup
   System.out.println(Arrays.toString(list(tree, args[0]).toArray()));
 }
}

This gets you use like:

$ java kidsOfMatchTheseDays leftish
[leftish, off-leftish-leaf]
$ java kidsOfMatchTheseDays root
[root, leftish, off-leftish-leaf, rightish-leafy]
$ java kidsOfMatchTheseDays rightish-leafy
[rightish-leafy]
$ java kidsOfMatchTheseDays a
[]

Questions:
Answers:

For example :

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



/**
 * 
 * @author X2
 *
 * @param <T>
 */
public class HisTree<T> 
{
    private Node<T> root;

    public HisTree(T rootData) 
    {
        root = new Node<T>();
        root.setData(rootData);
        root.setChildren(new ArrayList<Node<T>>());
    }

}

class Node<T> 
{

    private T data;
    private Node<T> parent;
    private List<Node<T>> children;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getParent() {
        return parent;
    }
    public void setParent(Node<T> parent) {
        this.parent = parent;
    }
    public List<Node<T>> getChildren() {
        return children;
    }
    public void setChildren(List<Node<T>> children) {
        this.children = children;
    }
}

Questions:
Answers:

Custom Tree implement of Tree without using the Collection framework. It contains different fundamental operation needed in Tree implementation.

class Node
{
int data;
Node left;
Node right;

public Node(int ddata, Node left, Node right)
{
    this.data = ddata;
    this.left = null;
    this.right =null;       
}

public void displayNode(Node n)
{
    System.out.print(n.data +" ");  
}
}

class BinaryTree
{
Node root;
public BinaryTree()
{
    this.root = null;
}
public void insertLeft(int parent,int leftvalue )
{
    Node n = find(root,parent);
    Node leftchild = new Node(leftvalue, null, null);
    n.left = leftchild;
}

public void insertRight(int parent, int rightvalue)
{
    Node n = find(root,parent);
    Node rightchild = new Node(rightvalue, null, null);
    n.right = rightchild;
}

public void insertRoot(int data)
{
    root = new Node(data, null, null);
}

public Node getRoot()
{
    return root;
}

public Node find(Node n,int key)
{       
    Node result = null;
    if (n == null)
        return null;
    if (n.data ==key)
        return n;
    if (n.left != null)
        result = find(n.left,key);
    if (result == null)
        result = find(n.right,key);
    return result;
} 

public int getheight(Node root)
{
    if(root == null)
        return  0;      
    return Math.max(getheight(root.left),getheight(root.right))+1; 
}

public void printTree(Node n)
{       
    if( n == null)
        return;
    printTree(n.left);
    n.displayNode(n);
    printTree(n.right);             
}
}

Questions:
Answers:

You can use the HashTree class included in Apache JMeter that is part of the Jakarta Project.

HashTree class is included in the package org.apache.jorphan.collections. Although this package is not released outside the JMeter project, you can get it easily:

1) Download the JMeter sources.

2) Create a new package.

3) Copy on it /src/jorphan/org/apache/jorphan/collections/ . All files except Data.java

4) Copy also /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree is ready to use.

Questions:
Answers:

Please check the below code, where I have used Tree data structures, without using Collection classes. The code may have bugs/improvements but please use this just for reference

package com.datastructure.tree;

public class BinaryTreeWithoutRecursion <T> {

    private TreeNode<T> root;


    public BinaryTreeWithoutRecursion (){
        root = null;
    }


    public void insert(T data){
        root =insert(root, data);

    }

    public TreeNode<T>  insert(TreeNode<T> node, T data ){

        TreeNode<T> newNode = new TreeNode<>();
        newNode.data = data;
        newNode.right = newNode.left = null;

        if(node==null){
            node = newNode;
            return node;
        }
        Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
        queue.enque(node);
        while(!queue.isEmpty()){

            TreeNode<T> temp= queue.deque();
            if(temp.left!=null){
                queue.enque(temp.left);
            }else
            {
                temp.left = newNode;

                queue =null;
                return node;
            }
            if(temp.right!=null){
                queue.enque(temp.right);
            }else
            {
                temp.right = newNode;
                queue =null;
                return node;
            }
        }
        queue=null;
        return node; 


    }

    public void inOrderPrint(TreeNode<T> root){
        if(root!=null){

            inOrderPrint(root.left);
            System.out.println(root.data);
            inOrderPrint(root.right);
        }

    }

    public void postOrderPrint(TreeNode<T> root){
        if(root!=null){

            postOrderPrint(root.left);

            postOrderPrint(root.right);
            System.out.println(root.data);
        }

    }

    public void preOrderPrint(){
        preOrderPrint(root);
    }


    public void inOrderPrint(){
        inOrderPrint(root);
    }

    public void postOrderPrint(){
        inOrderPrint(root);
    }


    public void preOrderPrint(TreeNode<T> root){
        if(root!=null){
            System.out.println(root.data);
            preOrderPrint(root.left);
            preOrderPrint(root.right);
        }

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTreeWithoutRecursion <Integer> ls=  new BinaryTreeWithoutRecursion <>();
        ls.insert(1);
        ls.insert(2);
        ls.insert(3);
        ls.insert(4);
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        //ls.preOrderPrint();
        ls.inOrderPrint();
        //ls.postOrderPrint();

    }

}

Questions:
Answers:

There is no specific data structure in Java which suits to your requirements. Your requirements are quite specific and for that you need to design your own data structure. Looking at your requirements anyone can say that you need some kind of n-ary tree with some specific functionality. You can design your data structure in following way:

  1. Structure of the node of the tree would be like content in the node and list of children like:
    class Node { String value; List children;}
  2. You need to retrieve the children of a given string, so you can have 2 methods 1: Node searchNode(String str), will return the node that has the same value as given input (use BFS for searching) 2: List getChildren(String str): this method will internally call the searchNode to get the node having same string and then it will create the list of all string values of children and return.
  3. You will also be required to insert a string in tree. You will have to write one method say void insert(String parent, String value): this will again search the node having value equal to parent and then you can create a Node with given value and add to the list of children to the found parent.

I would suggest, you write structure of the node in one class like Class Node { String value; List children;} and all other methods like search, insert and getChildren in another NodeUtils class so that you can also pass the root of tree to perform operation on specific tree like:
class NodeUtils{ public static Node search(Node root, String value){// perform BFS and return Node}

Questions:
Answers:

In the past I have just used a nested map for this. This is what I use today, it is very simple but it fits my needs. Maybe this will help another one.

import com.fasterxml.jackson.annotation.JsonValue;
import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created by kic on 16.07.15.
 */
public class NestedMap<K, V> {
    private final Map root = new HashMap<>();

    public NestedMap<K, V> put(K key) {
        Object nested = root.get(key);

        if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
        return (NestedMap<K, V>) nested;
    }

    public Map.Entry<K,V > put(K key, V value) {
        root.put(key, value);

        return (Map.Entry<K, V>) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
    }

    public NestedMap<K, V> get(K key) {
        return (NestedMap<K, V>) root.get(key);
    }

    public V getValue(K key) {
        return (V) root.get(key);
    }

    @JsonValue
    public Map getRoot() {
        return root;
    }

    public static void main(String[] args) throws Exception {
        NestedMap<String, Integer> test = new NestedMap<>();
        test.put("a").put("b").put("c", 12);
        Map.Entry<String, Integer> foo = test.put("a").put("b").put("d", 12);
        test.put("b", 14);
        ObjectMapper mapper = new ObjectMapper();
        System.out.println(mapper.writeValueAsString(test));

        foo.setValue(99);
        System.out.println(mapper.writeValueAsString(test));

        System.out.println(test.get("a").get("b").getValue("d"));
    }
}

Questions:
Answers:
    // TestTree.java
// A simple test to see how we can build a tree and populate it
//
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;

public class TestTree extends JFrame {

  JTree tree;
  DefaultTreeModel treeModel;

  public TestTree( ) {
    super("Tree Test Example");
    setSize(400, 300);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }

  public void init( ) {
    // Build up a bunch of TreeNodes. We use DefaultMutableTreeNode because the
    // DefaultTreeModel can use it to build a complete tree.
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");
    DefaultMutableTreeNode subroot = new DefaultMutableTreeNode("SubRoot");
    DefaultMutableTreeNode leaf1 = new DefaultMutableTreeNode("Leaf 1");
    DefaultMutableTreeNode leaf2 = new DefaultMutableTreeNode("Leaf 2");

    // Build our tree model starting at the root node, and then make a JTree out
    // of it.
    treeModel = new DefaultTreeModel(root);
    tree = new JTree(treeModel);

    // Build the tree up from the nodes we created.
    treeModel.insertNodeInto(subroot, root, 0);
    // Or, more succinctly:
    subroot.add(leaf1);
    root.add(leaf2);

    // Display it.
    getContentPane( ).add(tree, BorderLayout.CENTER);
  }

  public static void main(String args[]) {
    TestTree tt = new TestTree( );
    tt.init( );
    tt.setVisible(true);
  }
}

Questions:
Answers:

I wrote a tree library that plays nicely with Java8 and that has no other dependencies. It also provides a loose interpretation of some ideas from functional programming and lets you map/filter/prune/search the entire tree or subtrees.

https://github.com/RutledgePaulV/prune

The implementation doesn’t do anything special with indexing and I didn’t stray away from recursion, so it’s possible that with large trees performance will degrade and you could blow the stack. But if all you need is a straightforward tree of small to moderate depth, I think it works well enough. It provides a sane (value based) definition of equality and it also has a toString implementation that lets you visualize the tree!

Questions:
Answers:

You can use TreeSet class in java.util.*. It is working like Binary search tree, so it is already sorted. TreeSet class implements Iterable, Collection and Set interfaces. You can traverse through the tree with iterator like a set.

TreeSet<String> treeSet = new TreeSet<String>();
Iterator<String> it  = treeSet.Iterator();
while(it.hasNext()){
...
}

You can check, Java Doc and some other .

Leave a Reply

Your email address will not be published. Required fields are marked *