Java Tree structure interview questions and coding questions -- Part 1

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5

Q6

Java does not have a Tree class but you can define one. In my 10+ years as a Java developer, I have rarely used a Tree structure,  but when I do use it I find it to be a bit more complicated than working with other data structure. I have also experienced and noticed that developer interview pre screening coding tests including Tree related coding questions. Especially the software houses. I guess this could be due to 2 reasons.

• To test your skills to work with recursion and iteration. Some people like me find it hard to work with recursion. Java coding questions frequently asked in technical tests and job interviews -- part 4: iteration Vs recursion.
• To test your ability to write code and work with the data structures.
• Parametrized Tree class with Java Generics can add complexity to some.

So, here is a  series of Java Tree related developer questions and answers.

Q. Can you create a Tree class that can work with different types like String, File, Person, etc and supports the follwing methods

• Tree add(T data) -- adds a child node to the parent node. 
• void remove (T data) -- removes a child node to the parent node. 
• Tree getRoot( ) -- returns the root of the tree.
• boolean contains(T data) -- searches the tree for a given type

A. This is a very basic question. The tree class should be parametrized with generics. Let's say this is T that can be substituted during compile-time for String, File, Person, etc. Let's use both iteration and recursion.

The tree structure needs both the parent and children to traverse top to bottom and bottom to top. Since it is a n-ary tree, that is a parent can have n number of children, we will use an ArrayList to store child nodes. 

Now, the Java code to represent the above diagram as simple as possible with the relevany methods.

package com.mycompany.app.tree;

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

public class Tree<T>
{
    private T data;
    private Tree<T> parent;
    private List<Tree<T>> children;
    
    public Tree(T data)
    {
        this.data = data;
        children = new ArrayList<Tree<T>>();
    }
    
    /**
     * Adds a new child node to the parent node returns the added Child
     */
    public Tree<T> addChild(T childData)
    {
        Tree<T> childNode = new Tree<T>(childData);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }
    
    /**
     * Removes a child node from a parent.
     */
    public void removeChild(T childData)
    {
        Tree<T> childNode = new Tree<T>(childData);
        this.children.remove(childNode);
    }
    
    /**
     * Returns the parent
     */
    public Tree<T> getParent()
    {
        return this.parent;
    }
    
    /**
     * Returns the parent
     */
    public Tree<T> getRoot()
    {
        if (this == null)
        {
            return this;
        }
        
        Tree<T> parentTmp = this.parent;
        Tree<T> root = this;
        
        //iteration
        while (parentTmp != null)
        {
            parentTmp = root.parent;
            if (parentTmp != null)
            {
                root = parentTmp;
            }
            
        }
        
        return root;
    }
    
    /**
     * Searches the tree for a given type
     */
    public boolean contains(T data)
    {
        
        if (this == null)
        {
            return false;
        }
        
        if (this.data.equals(data))
        {
            return true;
        }
        
        List<Tree<T>> children2 = this.children;
        Iterator<Tree<T>> iterator = children2.iterator();
        while (children2 != null && iterator.hasNext())
        {
            Tree<T> next = iterator.next();
            if (next != null)
            {
                next.contains(data); //recursion
            }
            
        }
        
        return false;
    }
    
    @Override
    public String toString()
    {
        StringBuilder output = new StringBuilder("[");
        helpToString(this, output, 0);
        output.append("]");
        return output.toString();
    }
    
    private void helpToString(Tree<T> tree, StringBuilder output, int level)
    {
        if (tree == null)
            return; // Tree is empty, so leave.
            
        output.append(getSpaces(level) + tree.data);
        
        List<Tree<T>> children2 = tree.children;
        ++level; //increment the level
        
        Iterator<Tree<T>> iterator = children2.iterator();
        while (children2 != null && iterator.hasNext())
        {
            Tree<T> next = iterator.next();
            if (next != null)
            {
                helpToString(next, output, level); //recursion
            }
            
        }
        
    }
    
    private String getSpaces(int level)
    {
        StringBuilder sb = new StringBuilder("\n");
        for (int i = 0; i < level; i++)
        {
            sb.append("--");
        }
        
        return sb.toString();
    }
    
}

Finally, the test class with the main method to keep it simple.

package com.mycompany.app.tree;

public class TreeTest
{
    public static void main(String[] args)
    {
        Tree<String> root = new Tree<String>("A");
        root.addChild("B");
        Tree<String> childC = root.addChild("C");
        root.addChild("D");
        
        Tree<String> childC1 = childC.addChild("C1");
        
        System.out.println("root = " + childC.getRoot());                 // toString() method is invoked
        System.out.println("Contains C = " + childC.contains("C"));
        System.out.println("Contains D = " + childC.contains("D"));
        
        System.out.println("root = " + childC1.getParent());              // toString() method is invoked
        
    }
}

The printed output is:

root = [
A
--B
--C
----C1
--D]
Contains C = true
Contains D = false
root = [
C
--C1]

More Java developer questions and answers on Tree data structure.

• Java Tree structure interview questions and coding questions -- Part 2
• Java Tree structure interview questions and coding questions -- Part 3
• Java Tree structure interview questions and coding questions -- Part 4