Binary Tree - 83: Print all paths where sum of all the node values of each path equals given value

Source Code:thecodingsimpl...
Solution:
- We start binary tree traversal in post order manner
- At every stage, we'll store node value in list
- Now once we're done with left & right traversal, we'll check elements from list & check if sum matches to given value
- If sum matches, print all values till end of list
- Once we do traversal for a node, we remove node from list
Time Complexity: O(n)
Space Complexity: O(n)
Do Watch video for more info
CHECK OUT CODING SIMPLIFIED
/ codingsimplified
★☆★ VIEW THE BLOG POST: ★☆★
thecodingsimpli...
I started my UA-cam channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 200+ videos.
★☆★ SUBSCRIBE TO ME ON UA-cam: ★☆★
www.youtube.co...
★☆★ Send us mail at: ★☆★
Email: [e-mail]

[@free-palestine000]

Hi sir great explanation but small correction, this looks like preorder since you are processing node first then recursing to left and right.

[@satishbahuguna3349]

Sir this is actually preorder traversal as we r printing node first then visiting left n right

[@AmanKumar-nz3jz]

amazing explanation thank you sir

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@mettudheeraj1393]

Correct me if i am wrong , how can the time complexity be linear it is quadratic i guess?

[@ujjwalmittal3785]

I am also having the same doubt. .
So do u get what is the complexity of this question ..?

[@krishnarajyadav3953]

Did you get the ans ?
GFG has given O( n * h * h) -> I think this is also wrong .

[@kushalsraj6759]

@@krishnarajyadav3953 I think it would be O(n^2) as if all nodes in a tree form a path then you'll have to traverse the tree once (n) and add all the paths second time (n) which is the worst case.

[@mukulsharma2791]

I think this solution won't print the case where there is a path from leaf to leaf.
For example : If the binary tree is 2,3,-1,1,3 (inorder) and the given key = 6, then your solution will print 1,3,2 but not -1,3,1,3

[@anandbalaji8136]

Sir,First we have traversed from the root node but as per the logic (Post Order)..we should have traversed from leaf node..Please correct me if I am wrong ..

[@CodingSimplified]

Even if you postorder, our starting point is root. The same thing is explained here.
Let me know if you've any questions on it further.

[@anandbalaji8136]

@@CodingSimplified thank you sir !

[@Dyslexic_Neuron]

instead of printing can u code to return the list ?

[@CodingSimplified]

Rather than printing, you can take a List. Following is the solution. Storing the values in 'finalList'. Let me know if you've any doubt once you see below solution:
package binarytree;
import java.util.ArrayList;
import java.util.List;
class Node {
Node left;
Node right;
int data;
}
class BinaryTree {
List elements = new ArrayList();
List finalList = new ArrayList();
public void printKPathEqualToSum(Node node, int val) {
if (node == null) {
return;
}
elements.add(node.data);
printKPathEqualToSum(node.left, val);
printKPathEqualToSum(node.right, val);
int sum = 0;

for (int i = elements.size() - 1; i >= 0; i--) {

sum = sum + elements.get(i);

if (sum == val) {
List newList = new ArrayList();

for (int j = i; j < elements.size(); j++) {
newList.add(elements.get(j));
}

finalList.add(newList);
}
}

elements.remove(elements.size() - 1);
}
public Node createNewNode(int val) {
Node newNode = new Node();
newNode.data = val;
newNode.left = null;
newNode.right = null;
return newNode;
}
}
public class BinaryTreeApp {
public static void main(String[] args) {
BinaryTree a = new BinaryTree();
Node root = a.createNewNode(2);
root.left = a.createNewNode(4);
root.left.left = a.createNewNode(1);
root.left.right = a.createNewNode(6);
root.right = a.createNewNode(5);
root.right.right = a.createNewNode(7);
a.printKPathEqualToSum(root, 6);
System.out.println(a.finalList);
}
}

[@sdeBack1]

How Tc is O(n)

[@kushalsraj6759]

Same question T(n)? Because we have a extra loop after traversing all elements in the tree.