Tree Structure and Recursion

Recursion while adding nodes in tree data structure

It isn't printing it right for the following reasons:

First, your add method is always printing "value is " + root.value", which is confusing when trying to figure out how the program adds values.

Second, your add method prints after the value has been inserted, I would restructure it so that it prints the value to be inserted first, and then the path in which the nodes are being checked:

    public void add(int value) {
    // you always printed out the value of the root node with every call to this method
    // I updated it to reflect the input argument
    System.out.println("\nvalue is " + value);
    root = addRecursive(root, value);
}

Now each block is its own insertion and the program flow is easier to trace.

Next: current is actually printing correctly, just in reverse order. Let us say you are inserting 5, the current nodes to be printed will be: the parent of 5, which is 4, then the parent of 4, which is 6.

This image might help to visualize the tree (sorry for my ugly hand writing) BST reverse order

If you want to change the order, do it like this (place the print of current before the if statement):

    private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    System.out.println("current is " + current.value);

    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
}

Furthermore, if you would like to see if your insertion into a binary search tree works, you can use this method to print your tree in ascending order:

    public void inOrderPrint(Node node){

    if (node.left != null) {
        inOrderPrint(node.left);
    }

    System.out.println(node.value);

    if (node.right != null) {
        inOrderPrint(node.right);
    }
}

And call it like this in your main:

    public static void main(String h[]) {
    TreeCheck bt = new TreeCheck();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);

    System.out.println("-------");
    bt.inOrderPrint(bt.root);

}

I hope that was helpful and that I explained it clearly. Please comment if I made an incorrect statement and I will edit the post accordingly.

How to get recursively get all leaves of a Tree Structure in Java

The problem can be solved in two steps as follows, where the notation is some Java-ish pseudocode. First, all of the database rows have to be put in a List<Node> Nodes, where Node should have an additional member ParentID and the actual tree structure has to be built. This can be done as follows in time O(n^2), which is not optimal, but makes no additional assumptions on the node indices.

for (int i = 0; i < Nodes.Count(); i++) // iterate nodes
{
    for (int j = 0; j < Nodec.Count(); j++) // search parent of i-th node
    {
        if (Nodes[j].id.Equals(Nodes[i].ParentID)) // j-th node is parent of i-th node
        {
            Nodes[j].sub.add(Nodes[i]); // add i-th node to children of j-th node
        }
    }
}

Afterwards, the leaves can be identified easily as these are the nodes which have no children.

for (int i = 0; i < Nodes.Count(); i++)
{
    if (Nodes[i].sub.Count() == 0) // i-th node is a leaf
    {
        // do something with a leaf
    }
}

Note that I am not too familiar with Java from the top of my head, but the algorithmic idea should be understandable.

given a tree structure, how do you use recursion to make it into a simple linked list in-place?

There are always different ways to iterate over a tree, as there are:

InOrder
PreOrder
PostOrder

You can choose either of them to form your list...

For example (pseudocode, PreOrder):

function treeToList(LinkedList l, Tree t)
    if(t not nil)
        l.add(t.element)
        treeToList(l, t.Left)
        treeToList(l, t.Right)
    endif
end function

Remenber: If you perfomed an InOrder on a binary search tree you would get the elements in sorted order.

Python recursion to sort list of tuples into tree structure

You can use recursion:

table = [('1', ''), ('1.1', '1'), ('2', ''), ('2.1', '2'), ('2.1.1', '2.1'), ('3', ''), ('3.1', '3'), ('4', ''), ('4.1', '4'), ('4.1.1', '4.1'), ('4.1.2', '4.1')]
def to_dict(d):
  return {'node_id':d, 'children':[*map(to_dict, [a for a, b in table if b == d])]}

result = [to_dict(a) for a, b in table if not b]

Output:

[{'node_id': '1', 'children': [{'node_id': '1.1', 'children': []}]}, {'node_id': '2', 'children': [{'node_id': '2.1', 'children': [{'node_id': '2.1.1', 'children': []}]}]}, {'node_id': '3', 'children': [{'node_id': '3.1', 'children': []}]}, {'node_id': '4', 'children': [{'node_id': '4.1', 'children': [{'node_id': '4.1.1', 'children': []}, {'node_id': '4.1.2', 'children': []}]}]}]

Edit: supposing your tuples in table have additional information:

table = [('1', '', 'someval0'), ('1.1', '1', 'someval1'), ('2', '', 'someval2'), ('2.1', '2', 'someval3'), ('2.1.1', '2.1', 'someval4'), ('3', '', 'someval5'), ('3.1', '3', 'someval6'), ('4', '', 'someval7'), ('4.1', '4', 'someval8'), ('4.1.1', '4.1', 'someval9'), ('4.1.2', '4.1', 'someval10')]
def to_dict(d):
  return {**(dict(zip(['node_id', 'name'], d))), 'children':[*map(to_dict, [(a, *c) for a, b, *c in table if b == d[0]])]}

result = [to_dict((a, *c)) for a, b, *c in table if not b]