Home
Depth First Search Algorithm to Compute the Longest Tree Sum Path From Root to Leaf
Tags:, , , , , , ,

Depth First Search Algorithm to Compute the Longest Tree Sum Path From Root to Leaf

January 19, 2021 No Comments algorithms, c / c++, DFS, python, recursive

Given a binary tree root, return the sum of the longest path from the root to a leaf node. If there are two equally long paths, return the larger sum.

Constraints
n ≤ 100,000 where n is the number of nodes in root

longest-tree-path-from-root-to-leaf Depth First Search Algorithm to Compute the Longest Tree Sum Path From Root to Leaf algorithms c / c++ DFS python recursive

Recursive Depth First Search Algorithm to Compute the Longest Tree Sum Path From Root to Leaf

We can do DFS aka Depth First Search Algorithm to Perform Recursive Search from Root to Leave passing down the number of nodes and their sum.

At any time, we find a longer path or a equivalent path but with larger sum, we record it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int computeLongestPath(Tree* root) {
    if (!root) return 0;
    int ans = 0;
    int maxSum = 0;
    function<void(Tree*, int, int)> dfs = [&](Tree* root, int sum, int count) {
        if (!root) {            
            return;
        }
        if (root->left == root->right) {
            if ((count > ans) || (count == ans) && (sum > maxSum)) {
                maxSum = sum;
                ans = count;
                return;
            }            
        }        
        if (root->left) {
            dfs(root->left, sum + root->left->val, count + 1);
        }
        if (root->right) {
            dfs(root->right, sum + root->right->val, count + 1);
        }
    };
    dfs(root, root->val, 1);
    return maxSum;
}
/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int computeLongestPath(Tree* root) {
    if (!root) return 0;
    int ans = 0;
    int maxSum = 0;
    function<void(Tree*, int, int)> dfs = [&](Tree* root, int sum, int count) {
        if (!root) {            
            return;
        }
        if (root->left == root->right) {
            if ((count > ans) || (count == ans) && (sum > maxSum)) {
                maxSum = sum;
                ans = count;
                return;
            }            
        }        
        if (root->left) {
            dfs(root->left, sum + root->left->val, count + 1);
        }
        if (root->right) {
            dfs(root->right, sum + root->right->val, count + 1);
        }
    };
    dfs(root, root->val, 1);
    return maxSum;
}

Using Python to do a Recursive DFS algorithm (with a much concise code):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def computeLongestPath(self, root):
        def rec(curr):
            if not curr:
                return (0, 0)
            bigger = max(rec(curr.left), rec(curr.right))
            # (number of nodes, sum of subtree)
            return (bigger[0] + 1, bigger[1] + curr.val)
 
        return rec(root)[1]
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def computeLongestPath(self, root):
        def rec(curr):
            if not curr:
                return (0, 0)
            bigger = max(rec(curr.left), rec(curr.right))
            # (number of nodes, sum of subtree)
            return (bigger[0] + 1, bigger[1] + curr.val)

        return rec(root)[1]

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
374 words
Last Post: Number Of Rectangles That Can Form The Largest Square
Next Post: Teaching Kids Programming - Search in a 2D Sorted Matrix

The Permanent URL is: Depth First Search Algorithm to Compute the Longest Tree Sum Path From Root to Leaf

Related posts:

  1. Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree (BST),...
  2. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  3. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  4. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  5. Teaching Kids Programming – Longest Even Value Path in Binary Tree using Recursive Depth First Search Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary tree root, return...
  6. Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  7. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  8. Teaching Kids Programming – Restore the Word from Rules Teaching Kids Programming: Videos on Data Structures and Algorithms Given a list of rules in...

Leave a Reply