JAVA - Finding depth of a tree...?

Question

We are given a file with 99999 lines. Each line of the file represents a single node and it contains four integer: key, value, left child key, right child key (in the order specified). Key is a unique identifier assigned to each node. This identifier is just the line number. Value is the integer value stored in the node of the tree. Left and Right children are keys of the two appropriate children of the node. If a left or right child key is equal to zero, the appropriate child does not exist. The root node of the tree has key one.


Here are the first 10 lines, for example:
1 75 2 4
2 68 6 7
3 58 9 10
4 88 12 15
5 28 18 19
6 27 21 22
7 24 24 25
8 5 28 29
9 69 31 34
10 61 37 38

For example, the first line of the file is 1 75 2 4. It means that value of the node with key 1 is 75, key (line of file) of the left child of this node is 2, and key of right child is 4. Note: not all nodes in the file are part of the tree. Some lines in the file are there just to confuse you. What is the depth of this tree? (Depth is defined as the total number of nodes along the longest path.)

So... this is what I have so far (and its not much):

import java.util.Scanner;
import java.io.File;

class depth
{
public static void main(String[]args) throws Exception
{
Scanner sc = new Scanner(new File("tree.input"));
public int size()
{
return(size(root));
}
private int size(Node node)
{
if (node == null) return(0);
else
{
return(size(node.left) + 1 + size(node.right));
}
}
}
}

I'm not sure how to use the file to input my tree into the program. Can someone please help me get started working on this? If you want, you can do the whole problem and post it here. I have to find the depth of this tree with Java. Thank you! :)

Answer 1

The first thing to do is to convert the file into an array with the "key" as the "index" of the array which contains a (value, left, right) object or tuple or list or array.



From that array, you can build the tree easily. Just traverse the array and attach the nodes to their respective trees. In some cases, you might find that it is impossible to attach certain nodes now as the parent have not yet been created, put that node aside first and attach that at later (hopefully when the parents have been created.)



After that use the many algorithm on the internet to find the trees.

Answer 2

Define a class to represent a node. It will have four integer fields, one for each of the four numbers on the line for the node. The first number is really not needed as you will see below.



Declare and allocate an array of 100,000 nodes. Open the input file and read each line, getting the four numbers on the line (this seems like the part you are having trouble with). Once you have the four numbers, use the first number as an index into the node array. Construct a new node using the other three numbers and assign that new node into the array at the position indicated by the first number.



Once you have this data structure built, it's just a matter of recursively traversing it to find the maximum depth from the root; something like this:



int maxDepth ( int nodeId )

{

if (nodeId == 0) return 0;

int leftDepth = maxDepth(nodes[nodeId].left);

int rightDepth = maxDepth(nodes[nodeId].right);

return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);

}



where you call this function with the node id of the root node (1).

Answer 3

Step a million: Create an array of the a hundred thousand Node factors needed to keep all the entries. you may desire to have the fields 'fee', 'leftIndex', and 'rightIndex'. you do no longer might desire to keep the considerable for each ingredient, using fact the considerable often is the index of that ingredient in this array. Step 2: Write a recursive approach. This set of rules will verify the intensity of any given subtree; you grant it with the index of its "root" node, and it determines the intensity at that node. hint - the intensity at a given node is the utmost of the depths of its 2 infants, plus one. If the two newborn-indexes are 0, then the intensity of that subtree is a million.