- DFS, Recursion, Stack, Tree, Tree Traversals

Print all the paths from root to leaf, with a specified sum in Binary tree

  import java.util.*;  class GFG {      static List result        = new ArrayList();          static class Node {        int data;        Node left, right;    };          static Node newNode(int data)    {        Node temp = new Node();        temp.data = data;        temp.left = temp.right = null;        return temp;    }              static void pathSumUtil(        Node node, int targetSum,        Stack stack)    {        if (node == null) {            return;        }        stack.push(node.data);          if (node.left == null            && node.right == null) {            if (node.data == targetSum) {                result.add(new ArrayList(stack));            }        }        pathSumUtil(node.left,                    targetSum – node.data,                    stack);        pathSumUtil(node.right,                    targetSum – node.data,                    stack);        stack.pop();    }              static List pathSum(        Node root,        int targetSum)    {        if (root == null) {            return result;        }          Stack stack = new Stack();        pathSumUtil(root, targetSum, stack);          return result;    }          public static void main(String[] args)    {          Node root = newNode(5);        root.left = newNode(4);        root.right = newNode(8);        root.left.left = newNode(11);          root.right.left = newNode(13);        root.right.right = newNode(4);        root.left.left.left = newNode(7);        root.left.left.right = newNode(2);        root.right.right.left = newNode(5);        root.right.right.right = newNode(1);                                                                                                           int K = 22;                          List result            = pathSum(root, K);                  if (result.isEmpty())            System.out.println(“NA”);        else            for (List l : result) {                System.out.println(l);            }    }}