Improving this binary tree algorithm complexity

Question

I need to find if all paths of a binary tree that can end(which means all paths that starts from the root and end to a node that has only one child or none) have lengths that differ by no more than one.

My working solution work like this: the function longestPath finds the longest path, the function checkLengths traverse all nodes keeping track of the length of the paths and every time a node with only one child or none is found it checks if the difference between the length of the current path and the length of the longest path is more than 1.

This solution has complexity O(2n) because at worst every node has to be visited twice, once for the longestPath function and once for the lengthCheck function. I would like to improve the solution to O(n) but I'm having an hard time figuring out how to do so.

Edit: my solution is still O(n) but I would like to optimize it to find the solution by visiting each node only once and not twice.

int lengthCheckFlag=1;
int maxLength=-1;

void longestPath(Node n,int currentLength){
    if(n==nullptr){
        return;
    }
    if(n->left==nullptr && n->right==nullptr){
        if(maxLength==-1){
        maxLength=currentLength;
        }
        else{
            if(currentLength>maxLength){
                maxLength=currentLength;
            }
        }
    }
    longestPath(n->left,currentLength+1);
    longestPath(n->right,currentLength+1);
}

void checkLengths(Node n,int currentLength){
    if(n==nullptr){
        return;
    }
    if(n->left==nullptr || n->right==nullptr){
        if(abs(maxLength-currentLength)>1){
        lengthCheckFlag=0;
        }
    }
    checkLengths(n->left,currentLength+1);
    checkLengths(n->right,currentLength+1);
}

bool lengthCheckWrapper(Node n){
    if(n==nullptr){
        return true;
    }
    longestPath(n,0);
    checkLengths(n,0);
    return lengthCheckFlag;
}

Code Update:

int maxP=-1;
int minP=-1;

void minmaxPaths(Node n,int currentLength){
    if(n==nullptr){
        return;
    }
    if(n->left==nullptr && n->right==nullptr){
        if(maxP==-1){
          maxP=currentLength;
          minP=currentLength;
        }
        else{
            if(currentLength>maxP){
                maxP=currentLength;
            }
            if(currentLength<minP){
                minP=currentLength;
            }
        }
    }
    minmaxPaths(n->left,currentLength+1);
    minmaxPaths(n->right,currentLength+1);
}

bool lengthCheckWrapper(Node n){
    if(n==nullptr){
        return true;
    }
    minmaxPaths(n,0);
    if(abs(minP-maxP)<=1){
       return true;
    }
    return false;
}

There is nothing as O(2n). It's a 2 pass O(n) but O(n) nonetheless. A small optimization that can be tangible if the number of end nodes is relatively small compared to the number of all nodes is to save the length of all root to end nodes as you dive for a dfs to find the longest path. After the fact, compare those saved lengths with the longest path. — user1984
– user1984, Commented Dec 13, 2021 at 10:50
The simplest thing to do would be, in a single pass, find both the maximum and minimum depths of a leaf node, and then check that minLength + 1>= maxLength. — kaya3
– kaya3, Commented Dec 13, 2021 at 11:06
In the problem statement, I read one child or none. In the code, I find n->left==nullptr && n->right==nullptr. — greybeard
– greybeard, Commented Dec 13, 2021 at 12:58
@greybeard that's correct, the longest path that goes from root to leaf is also the longest path that goes from root to a node with one child or none. — Spyromancer
– Spyromancer, Commented Dec 13, 2021 at 14:06
@kaya3 is it possible to find both the minimum and maximum depths in a single function traversing each node only once? I know how to find both in separate functions but not both at once. — Spyromancer
– Spyromancer, Commented Dec 13, 2021 at 14:31

trincot · Accepted Answer · 2021-12-13 18:35:16Z

0

Some remarks:

O(2n) is the same as O(n)
Your functions use different conditions for identifying the potential end of a path: one uses a && operator (wrong) and the other uses a || operator (correct)

One idea for an alternative algorithm is to make a breadth first traveral. This is interesting, since the constraint really means that all non-perfect nodes (i.e. that have at most one child) must appear in the bottom two levels of the tree.

By consequence, if we find 2 more levels after the first level where we find a non-perfect node, then we have a violation and can stop the traversal.

The down side is that it uses more memory.

Here is how it could be implemented:

int minmaxDepth(Node root) {
    if (root == nullptr) {
        return 1; // OK
    }
    std::vector<Node> level, nextLevel;
    level.push_back(root);
    int minDepth = INT_MAX;
    int currDepth = 0;
    while (level.size()) {
        currDepth++;
        nextLevel = {};
        for (auto & parent : level) {
            if (currDepth < minDepth  && 
                    (parent->left == nullptr || parent->right == nullptr)) {
                minDepth = currDepth; // Found a path with minimal length
            }
            if (parent->left != nullptr) {
                nextLevel.push_back(parent->left);
            }
            if (parent->right != nullptr) {
                nextLevel.push_back(parent->right);
            }
            if (nextLevel.size() && currDepth > minDepth) {
                return 0; // Paths have lengths that differ more than 1
            }
        }
        level = nextLevel;
    }
    return 1; // All nodes were visited: no violation found
}

answered Dec 13, 2021 at 18:35

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

user1196549 Over a year ago

There is also a depth-first solution.

trincot Over a year ago

Yes, @Yves, the Asker's version is depth-first.

user1196549 Over a year ago

Why do you tell this ? The OP's method is not satisfactory.

trincot Over a year ago

@Yves, I indicated in my answer what needs correction in their code, but their idea of depth-first is fine.

user1196549 Over a year ago

Sorry to insist, but I don't see how this reduces the number of tests from 2n to n in the OP's method.

|

user1196549 · Accepted Answer · 2021-12-13 19:27:31Z

0

There is no need to pre-compute the longest path. Compute all path lengths and on the fly,

store the first length,
if some other length differs by more than one, you are done;
else store the differing length, and if any other length differs from the two stored ones, you are done.

answered Dec 13, 2021 at 19:27

user1196549

Collectives™ on Stack Overflow

Improving this binary tree algorithm complexity

2 Answers 2

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related