21. Diagonal sum in binary tree

The problem can be found at the following link: Question Link

My Approach

• Define a function diagonalSum that takes the root of a binary tree as input.

• Initialize an empty vector ans to store diagonal sums.

• Implement a Depth-First Search (DFS) function dfs using a lambda function:

  • Traverse the tree recursively.

  • Maintain the current diagonal level.

  • At each node:

    • Update the sum of the current diagonal level in ans.

    • Recur for the left child with cur + 1 as the diagonal level.

    • Recur for the right child with the same diagonal level cur.

• Invoke dfs with the root node and diagonal level 0.

• Return the ans vector containing diagonal sums.

Time and Auxiliary Space Complexity

• Time Complexity: The time complexity of this approach is O(N), where N is the number of nodes in the binary tree.

• Auxiliary Space Complexity: The auxiliary space complexity is O(N), where N is the number of nodes in the binary tree.

Code (C++)

class Solution {
  public:
    vector<int> diagonalSum(Node* root)
    {
        vector<int> ans;
        function<void(Node *, int)> dfs = [&](Node * node, int cur)
        {
            if(!node)
                return;
            if(cur==ans.size())
                ans.push_back(node -> data);
            else ans[cur] += node -> data;
            dfs(node->left, cur+1);
            dfs(node->right, cur);
        };
        dfs(root, 0);
        return ans;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.