Woodstock Blog

a tech blog for general algorithmic interview questions

[CC150v4] 4.8 Print Path Sum to Value


You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.


Keep a list of items as buffer, and check the following condition:

“does this node complete a path with the sum?”

There’re n nodes in total, and the max size of buffer is lg(n), so the time complexity is O(nlgn).


written by me

public static void find(TreeNode head, int target) {
    findSum(head, target, new ArrayList<Integer>());

private static void findSum(TreeNode node, int target, List<Integer> buffer) {
    if (node == null)

    int sum = 0;
    for (int i = buffer.size() - 1; i >= 0; i--) {
        sum += buffer.get(i);
        if (sum == target) {
            // from (i)th element until the last element is a valid path
            printPath(buffer, i);

    List<Integer> clone1 = new ArrayList<Integer>(buffer);
    findSum(node.left, target, clone1);

    List<Integer> clone2 = new ArrayList<Integer>(buffer);
    findSum(node.right, target, clone2);

private static void printPath(List<Integer> buffer, int start) {
    System.out.print("Path: ");
    for (int i = start; i < buffer.size(); i++) {
        System.out.print(buffer.get(i) + " ");