Given a Binary Tree and an integer number k. Write a function to print every pat

Question

Given a Binary Tree and an integer number k. Write a function to print every path in the tree that sum of the nodes in the path is k. Let assume a path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree. Example: Input: k = 5 output: 3 rightarrow 2 3 rightarrow 1 rightarrow 1 1 rightarrow 3 rightarrow 1 4 rightarrow 1 1 rightarrow -1 rightarrow 4 rightarrow 1 -1 rightarrow 4 rightarrow 2 5 1 rightarrow -1 rightarrow 5

Explanation / Answer

// This function prints all paths that have sum k

void printKPathUtil(Node *root, vector<int>& path,

                                           int k)

{

    // empty node

    if (!root)

        return;

    // add current node to the path

    path.push_back(root->data);

    // check if there's any k sum path

    // in the left sub-tree.

    printKPathUtil(root->left, path, k);

    // check if there's any k sum path

    // in the right sub-tree.

    printKPathUtil(root->right, path, k);

    // check if there's any k sum path that

    // terminates at this node

    // Traverse the entire path as

    // there can be negative elements too

    int f = 0;

    for (int j=path.size()-1; j>=0; j--)

    {

        f += path[j];

        // If path sum is k, print the path

        if (f == k)

            printVector(path, j);

    }

    // Remove the current element from the path

    path.pop_back();

}

// A wrapper over printKPathUtil()

void printKPath(Node *root, int k)

{

    vector<int> path;

    printKPathUtil(root, path, k);

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.