CODEWITHSUNDEEP
c++algorithmrecursiontreebinary-tree
blank space
blank space

Reputation: 97

Max sum root to leaf binary tree time complexity

int ma = INT_MIN;
int parent[1000];

int findMaxPath(struct node * ptr) {
    if (ptr == NULL) return 0;
    if (ptr->left == NULL && ptr->right == NULL) {
        // means leaf node
        int sum = ptr->data;
        int temp = ptr->data;
        while (parent[temp] != -1) {
            sum = sum + parent[temp];
            temp = parent[temp];
        }
        if (sum > ma)
            ma = sum;
    }
    else{
        if (ptr->left != NULL)
            parent[ptr->left->data] = ptr->data;
        if (ptr->right != NULL)
            parent[ptr->right->data] = ptr->data;
        findMaxPath(ptr->left);
        findMaxPath(ptr->right);
    }
}

Approach - Once i identify the leaf node I use the parent array to traceback to root node and sum all the values and if this sum value is greater than max value update the max value. I am not sure about the time complexity of this code Can you please help me with the time complexity of this code?

Upvotes: 2

Views: 1120

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

In a balanced tree the complexity is O(N*log(N)), because half of all nodes are leaves, and traversing back to the root takes log(N). If the tree is unbalanced, your speed could degrade to O(N2).

You can fix your approach by storing the sum in each node that you encounter, in which case the time complexity is going to be the O(n), because you never recompute root-to-node sums that you have computed once.

Another way to make this linear is by running a BFS or DFS from the root, and computing the sum for each vertex. DFS implementation is very simple:

int max_sum(node *n, int partial) {
    if (n == NULL) {
        return partial;
    }
    int my_sum = partial + n->value;
    return max(max_sum(n->left, my_sum), max_sum(n->right, my_sum));
}

// Running the code:
int maxSumInTree = max_sum(root, 0);

Upvotes: 1

amit
amit

Reputation: 178411

Time complexity varies a lot according to the tree's structure.

  • For balanced tree, each path from root to leaf is at most of O(logn), and there are no more than n leaves (obviously), so O(nlogn)
  • For a tree which is a single chain with a single leaf - it's O(n), since you do it at most once.
  • For a tree where each right subtree is of height exactly one, it's O(n^2), because you sum length of paths which are increasing: 1 + 2 + ... + n/2, which is in O(n^2) from sum of arithmetic progression.

Worst case of the algorithm is O(n^2), since there could be no more than n leaves, and each of at depth no more than n - which gives upper bound of O(n^2), and from the examples - we see this bound is tight.

Average Case of the algorithm is O(nlogn), since tree's average height is logarithmic.

An improvement solution with O(n) time and O(h) space could be a DFS, where local partial sum is stored and calculated, and when encountering "better" solution, just edit pointers needed to get to the "better" solution.

Upvotes: 3

Related Questions