CODEWITHSUNDEEP
iosobjective-calgorithmbreadth-first-searchdepth-first-search
Johnny Rockex
Johnny Rockex

Reputation: 4196

Find longest path between root node and any child

I have an array of elements, some of whom have children, who have children in turn and so on. I know the direct children of each element, and have a list of all descendents for each element. 

-(NSMutableArray *)descendents:(Element *)e {

    NSMutableArray * descendents = [NSMutableArray new];
    for (NSString * uID in e.children){
        [descendents addObject:uID];
        Element * k = elements[uID][@"element"];
        [descendents addObjectsFromArray:[self descendents:k]];
    }
    return descendents;
}

I can determine the root element by comparing the total number of descendents for each element. I can find the shortest route between the root and any given element given this:

-(int)find:(NSString *)uniqueID forElement:(Element *)e {

    int distance = 0;
    if ([e.children containsObject:uniqueID]){ //immediate child

        distance ++; //increment distance
        return distance; //return

    } else if ([e.descendents containsObject:uniqueID]){ //grand child etc

        distance ++;
        for (NSString * uID in e.children){
            Element * k = elements[uID][@"element"];
            distance += [self find:uniqueID forElement:k];
            return distance;
        }
    }

    return 0;
}

What I want to do is find the longest distance between an element and the root. I'm thinking about going back up the tree from elements with zero children or adding an array of distances between elements in the mapping function. Struggling as to the cleanest approach - any ideas?

EDIT: solution based on user3290797's answer below, tracking reference to max number of parents:

-(int)parentHeight:(NSString *)uID {

    int maxHeight = 0;
    Element * e = elements[uID][@"element"];
    for (NSString * parentID in e.parents){
        int height = [self parentHeight:parentID];
        maxHeight = (height > maxHeight) ? height : maxHeight;
    }
    return maxHeight + 1;
}

enter image description here

Upvotes: 0

Views: 188

Answers (2)

Anton
Anton

Reputation: 3203

The longest distance between an element and the root is called the height (or depth) of the tree.

One way to find it is to recursively traverse the tree and calculate the height of every node as the maximum of its children's heights plus one.

In pseudocode:

function height(node) {
    maxChildHeight = 0
    for(child in node.children) {
        h = height(child)
        if(h > maxChildHeight) {
            maxChildHeight = h
        }
    }
    return maxChildHeight + 1
}

Upvotes: 1

jesusgn90
jesusgn90

Reputation: 569

If not a lot of nodes, calculate each distance and assign an ID for each , then check the longest of them , this is slow but works hahaha

Upvotes: 1

Related Questions