CODEWITHSUNDEEP
javaalgorithmrecursiondata-structurestree
Pazuzu
Pazuzu

Reputation: 303

Computing the height of a tree - Java

I currently have a method which computes the height of a tree but I need to speed up the algorithm so that it may run under 6 seconds. I was thinking of implementing something recursive but unsure of how to do so.

public class TreeHeight {
    int n;
    int parent[];

    void read() throws IOException {
        FastScanner in = new FastScanner();
        n = in.nextInt();
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = in.nextInt();
        }
    }

    int computeHeight() {
                    // Replace this code with a faster implementation
        int maxHeight = 0;
        for (int vertex = 0; vertex < n; vertex++) {
            int height = 0;
            for (int i = vertex; i != -1; i = parent[i])
                height++;
            maxHeight = Math.max(maxHeight, height);// assign the max of the two arguements
        }
        return maxHeight;
    }
}

Upvotes: 1

Views: 2969

Answers (4)

Valar Morghulis
Valar Morghulis

Reputation: 687

Just a follow-up comment/note for anyone that needs a faster algorithm than the one mentioned by @Paul Boddington.

(A friend used above algorithm for a class assignment, found it's not fast enough to pass the time limit).

We don't need to walk through to the root node every time, just stop at the first node that is already calculated.

So the most important diffences are two lines:

            while self.heights[i] == 0 and i != -1:

to replace the above algorithm:

        for (int i = vertex; i != -1; i = parent[i]) {

Sample Python Code:

class TreeHeight:
def read(self):
    self.parent = []  // input parent array
    self.n = len(self.parent)
    self.heights = [0] * self.n

def get_root(self):
    return self.parent.index(-1)

def compute_height(self):
    # Replace this code with a faster implementation

    maxHeight = 0
    for vertex in range(self.n):
        if self.heights[vertex] != 0:
            continue

        if self.parent[vertex] == -1:
            self.heights[vertex] = 1

        height = 0
        i = vertex
        while self.heights[i] == 0 and i != -1:
            height += 1
            i = self.parent[i]
        height += self.heights[i]

        maxHeight = max(maxHeight, height)

        i = vertex
        while self.heights[i] == 0 and i != -1:
                  self.heights[i] = height
                  height = height - 1
                  i = self.parent[i]

        print vertex, self.heights[vertex]
        print "maxHeight", maxHeight

    return maxHeight

Upvotes: 0

batman007
batman007

Reputation: 39

if you think logically

height of a tree=max(height of left subtree ,rightsubtree)+1

so a recursive approach would be recursively compute the height of left and right subtree and return max+1.

here is what the function looks like

int Height(Node root)
{

    if(root==null)
     return 0;

 int l=Height(root.left);
 int r=Height(root.right);

return max(l,r)+1;
}

see if this recursive solution works for you.

Upvotes: 0

Paul Boddington
Paul Boddington

Reputation: 37665

You could improve your algorithm using memoization. I have used an array heights to store already calculated results. Whenever a result is calculated, it is stored in the array and not calculated again. This could make your algorithm significantly faster for huge arrays.

int computeHeight() {
    int maxHeight = 0;
    int[] heights = new int[parent.length];
    for (int vertex = 0; vertex < n; vertex++) {
        if (heights[vertex] != 0)       // We've been here before
            continue;
        int height = 0;
        for (int i = vertex; i != -1; i = parent[i]) {
            if (heights[i] != 0) {     // We've been here before 
                height += heights[i];   
                break;
            }
            height++;
        }
        maxHeight = Math.max(maxHeight, height);
        // Now we store the results in the array to save us time in the future.
        for (int i = vertex; i != -1; i = parent[i]) {
            if (heights[i] != 0)
                break;
            heights[i] = height--;
        }
    }
    return maxHeight;
}

Upvotes: 3

Sara S
Sara S

Reputation: 679

A recursive solution could look something like this, depending on how you store your tree internally. This solution assumes you have a class Node that has links to all its node children.

What the code does, it computes from the root recursively the height (or actually depth) of each path downwards in the tree, and chooses the longest path.

int computeHeight(Node root){
    int levels = 0;
    for(Node child : root.children){
        int childHeight = computeHeight(child);
        if(childHeight > levels){
            levels = childHeight;
        }
    }
    return levels + 1;
}

Upvotes: 3

Related Questions