K — Sum Path In A Binary Tree

Coding Ninjas Studio

Photo by kazuend on Unsplash

PROBLEM STATEMENT:

A binary tree and a number k are given. Return every path in the tree with sum of the nodes in the path as k.

APPROACH:

1. Function Signature:
The function takes a Binary Tree’s root node and an integer `k` as parameters and returns a vector of vectors of integers (`vector<vector<int>>`) representing all paths in the binary tree where the sum of node values equals `k`.

2. Helper Function:
This recursive helper function is responsible for exploring all paths in the binary tree and identifying paths whose sum is equal to `k`. It utilizes backtracking to keep track of the current path.

3. Base Case:
If the current node is `NULL`, it means the end of a path has been reached, so the function returns.

4. Update Current Path:
Add the current node’s value to the path.

5. Recursion for Left and Right Subtrees:
Recursively call the `solve` function for the left and right subtrees.

6. Check Sum and Record Paths:

Calculate the sum of the current path in reverse order. If the sum equals `k`, record the path from the current index (`j`) to the end of the path in a temporary vector and add it to the result (`ans`).

7. Backtrack:
Remove the last element from the path to backtrack and explore other paths.

Initialize an empty result vector (`ans`) and an empty path vector (`path`). Call the `solve` function to explore paths in the binary tree and return the final result.

This approach effectively explores all paths in the binary tree using a recursive depth-first traversal, and it uses backtracking to handle different paths. The sum of each path is checked, and valid paths are recorded in the result vector.

CODE:

#include <bits/stdc++.h>
using namespace std;
    
    template <typename T>
    class BinaryTreeNode {
    public:
        T data;
        BinaryTreeNode<T> *left;
        BinaryTreeNode<T> *right;

        BinaryTreeNode(T data) {
            this->data = data;
            left = NULL;
            right = NULL;
        }
    };


template <typename T>
void solve(vector<vector<T>> &ans, vector<T> &path, BinaryTreeNode<T> *root, T k) {
    if (root == NULL) {
        return;
    }
    path.push_back(root->data);
    solve(ans, path, root->left, k);
    solve(ans, path, root->right, k);

    T sum = 0;
    for (int j = path.size() - 1; j >= 0; j--) {
        sum += path[j];
        if (sum == k) {
            // Record the path from j to the end
            vector<T> temp;
            for (int i = j; i < path.size(); i++) {
                temp.push_back(path[i]);
            }
            ans.push_back(temp);
        }
    }
    path.pop_back();
}

template <typename T>
vector<vector<T>> kPathSum(BinaryTreeNode<T> *root, T k) {
    vector<vector<T>> ans;
    vector<T> path;
    solve(ans, path, root, k);
    return ans;
}

// Driver's code for testing
int main() {
    // Create a sample binary tree
    BinaryTreeNode<int> *root = new BinaryTreeNode<int>(10);
    root->left = new BinaryTreeNode<int>(5);
    root->right = new BinaryTreeNode<int>(12);
    root->left->left = new BinaryTreeNode<int>(4);
    root->left->right = new BinaryTreeNode<int>(7);

    int k = 22;

    // Find paths with sum equal to k
    vector<vector<int>> result = kPathSum(root, k);

    // Display the result
    cout << "Paths with sum " << k << ": \n";
    for (const auto &path : result) {
        for (const auto &nodeValue : path) {
            cout << nodeValue << " ";
        }
        cout << "\n";
    }

    // Clean up memory (free the allocated nodes)
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}