513. Find Bottom Left Tree Value

Recursive, using global variable

class Solution {
    private int maxDepth = -1;
    private int res;

    private void travHelper(TreeNode root, int level) {
        // if null, which should not happen
        if (root == null) return;

        // if leaf
        if (root.left == null && root.right == null) {
            if (level > maxDepth) {
                maxDepth = level;
                res = root.val;
            }
        }

        travHelper(root.left, level + 1);
        travHelper(root.right, level + 1);
    }

    public int findBottomLeftValue(TreeNode root) {
        // root cannot be null

        res = root.val;

        travHelper(root, 1);

        return res;
    }
}

Recursive, not using global variable

use a Pair of Integers as the return value for recursion (can alternatively use int[]

// using Pair<Integer, Integer>
class Solution {

    private Pair<Integer, Integer> travHelper(TreeNode root, int level) {
        // if null, which should not happen
        if (root == null) return null;

        // if leaf
        if (root.left == null && root.right == null) {
            return new Pair<>(level, root.val);
        }

        Pair<Integer, Integer> leftRes = (root.left != null) ? travHelper(root.left, level + 1) : null;
        Pair<Integer, Integer> rightRes = (root.right != null) ? travHelper(root.right, level + 1) : null;

        if (root.left == null) {
            return rightRes;
        } else if (root.right == null) {
            return leftRes;
        } else {
            if (leftRes.getKey() >= rightRes.getKey()) return leftRes;
            return rightRes;
        }
    }

    public int findBottomLeftValue(TreeNode root) {
        return travHelper(root, 1).getValue();
    }
}

// using int[]
class Solution {

    private int[] travHelper(TreeNode root, int level) {
        // if null, which should not happen
        if (root == null) return null;

        // if leaf
        if (root.left == null && root.right == null) {
            return new int[] {level, root.val};
        }

        int[] leftRes = (root.left != null) ? travHelper(root.left, level + 1) : null;
        int[] rightRes = (root.right != null) ? travHelper(root.right, level + 1) : null;

        if (root.left == null) {
            return rightRes;
        } else if (root.right == null) {
            return leftRes;
        } else {
            if (leftRes[0] >= rightRes[0]) return leftRes;
            return rightRes;
        }
    }

    public int findBottomLeftValue(TreeNode root) {
        return travHelper(root, 1)[1];
    }
}

Iterative (level order traversal)

a bit different from the generic level order traversal:
- use nextLevel to check for stop condition, as need to keep curLevel to retrieve first node
- start off defining the nextLevel with root before entering into loop (because need to do curLevel = nextLevel upfront rather than at the end of the loop, otherwise curLevel will be overwritten with null and cannot be used to retrieve first node)
- can use do…while to avoid writing curLevel = nextLevel outside the loop too

class Solution {

    public int findBottomLeftValue(TreeNode root) {
        // root cannot be null

        Deque<TreeNode> nextLevel = new ArrayDeque<>(List.of(root));
        Deque<TreeNode> curLevel;

        do {
            curLevel = nextLevel;
            nextLevel = new ArrayDeque<>();
            for (TreeNode node : curLevel) {
                if (node.left != null) nextLevel.add(node.left);
                if (node.right != null) nextLevel.add(node.right);
            }
        } while (!nextLevel.isEmpty());

        return curLevel.peek().val;
    }
}

112. Path Sum

Recursive

class Solution {
    public boolean sumHelper(TreeNode root, int targetSum, int curSum) {
        if (root == null) return false;

        if (root.left == null && root.right == null) return (targetSum == curSum + root.val);

        return sumHelper(root.left, targetSum, curSum + root.val) || sumHelper(root.right, targetSum, curSum + root.val);
    }

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

Can do better if we use parameter to record “left over” value - don’t even need a helper function

TargetSum to refer to “target sum from me to leaf”

class Solution {

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

        if (root.left == null && root.right == null) return (targetSum == root.val);

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

Iterative

the reason we can use pre-order traversal is that we essentially do the check at leaf nodes; the ‘process’ can be seen as ‘adding the value of current node to sum’; no need for backtracking (return the OR result, so don’t have to have the result of both subtrees - true at any node will return a true, and only return false when none is true at the end)

class Solution {

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        
        // the integer will store the sum up to (including) the current node
        Deque<Pair<TreeNode, Integer>> st = new ArrayDeque<>();
        st.push(new Pair<>(root, root.val));

        while (!st.isEmpty()) {
            Pair<TreeNode, Integer> curPair = st.pop();
            TreeNode curNode = curPair.getKey();
            
            // if the curNode is leaf, check for sum equality
            if (curNode.left == null && curNode.right == null && curPair.getValue() == targetSum) return true;

            if (curNode.right != null) st.push(new Pair<>(curNode.right, curPair.getValue() + curNode.right.val));
            if (curNode.left != null) st.push(new Pair<>(curNode.left, curPair.getValue() + curNode.left.val));
        }

        return false;
    }
}