To see the question, click here.

Naive Approach

The idea is to maintain two stacks nodeStack and sumStack . Until nodeStack is empty; if it's a leaf node and the current sum equals 0, we found a path. Process the right child by pushing it onto the nodeStack and push the difference between the current sum and the right child's value onto the sumStack . Process the left child by pushing it onto the nodeStack and push the difference between the current sum and the left child's value onto the sumStack .

// TC: O(n)
// SC: O(n)

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class PathSum {
    public boolean helper(TreeNode root, int targetSum, int currSum) {
        if (root == null) {
            return false;
        }

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();

        nodeStack.push(root);
        sumStack.push(targetSum - root.val);

        while (!nodeStack.isEmpty()) {
            TreeNode currentNode = nodeStack.pop();
            int currentSum = sumStack.pop();

            if (currentNode.left == null && currentNode.right == null && currentSum == 0) {
                return true;
            }

            if (currentNode.right != null) {
                nodeStack.push(currentNode.right);
                sumStack.push(currentSum - currentNode.right.val);
            }

            if (currentNode.left != null) {
                nodeStack.push(currentNode.left);
                sumStack.push(currentSum - currentNode.left.val);
            }
        }

        return false;
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        return helper(root, targetSum, targetSum - root.val);
    }

    public static void main(String args[]) {
        PathSum ps = new PathSum();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        System.out.println(ps.hasPathSum(root, 22));
    }
}

Performance

The time complexity of the hasPathSum method is O(n) because we visit each node in the binary tree once. The space complexity is also O(n) because, in the worst-case scenario, the stack can contain all the nodes of the binary tree.

Refined Approach

Instead of maintaining two stacks, it is possible to use a single stack by maintaining a custom object that holds both the current node and the remaining sum.

// TC: O(n)
// SC: O(n)

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class StackNode {
    TreeNode node;
    int remainingSum;

    StackNode(TreeNode node, int remainingSum) {
        this.node = node;
        this.remainingSum = remainingSum;
    }
}

class PathSum {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        Stack<StackNode> stack = new Stack<>();
        stack.push(new StackNode(root, targetSum - root.val));

        while (!stack.isEmpty()) {
            StackNode current = stack.pop();
            TreeNode currentNode = current.node;
            int currentSum = current.remainingSum;

            if (currentNode.left == null && currentNode.right == null && currentSum == 0) {
                return true;
            }

            if (currentNode.right != null) {
                stack.push(new StackNode(currentNode.right, currentSum - currentNode.right.val));
            }

            if (currentNode.left != null) {
                stack.push(new StackNode(currentNode.left, currentSum - currentNode.left.val));
            }
        }

        return false;
    }

    public static void main(String args[]) {
        PathSum ps = new PathSum();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        System.out.println(ps.hasPathSum(root, 22));
    }
}

Performance

The time complexity of the hasPathSum method is O(n) because we visit each node in the binary tree once. The space complexity is also O(n) in the worst-case scenario where the binary tree is skewed and all nodes are pushed onto the stack.

Efficient Approach

We will use the Tree DFS Recursive approach to solve this problem. Initially, set the current sum to 0. If the root is null, return false. Otherwise, update the current sum with the value of the current node. If it's a leaf node, check if the current sum equals the target sum. Recursively check the left and right subtrees.

// TC: O(n)
// SC: O(n)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class PathSum {
    public boolean helper(TreeNode root, int targetSum, int currSum) {
        if (root == null) {
            return false;
        }

        currSum += root.val;

        if (root.left == null && root.right == null) {
            return currSum == targetSum;
        }

        return helper(root.left, targetSum, currSum) || helper(root.right, targetSum, currSum);
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        return helper(root, targetSum, 0);
    }

    public static void main(String args[]) {
        PathSum ps = new PathSum();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        System.out.println(ps.hasPathSum(root, 22));
    }
}

Performance

The time complexity of the hasPathSum method is O(n) because we visit each node in the binary tree once. The space complexity is also O(n) because the recursive calls will use space on the call stack proportional to the tree's height, which can be at most n in the worst case for a skewed tree.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.