Module Week 5

Path Sum

LeetCode 112

Easy ▼

Source

LeetCode 112 - Path Sum

Problem

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.

Function Signature

hasPathSum(root: TreeNode, targetSum: int) -> boolean

Examples

Input: root = [5 | 4, 8 | 11, null, 13, 4 | 7, 2, null, null, null, 1], targetSum = 22
Tree:
      5
     / \
    4   8
   /   / \
  11  13  4
/  \       \
7    2       1
Output: true | Explanation: path 5 -> 4 -> 11 -> 2 sums to 22

Input: root = [1 | 2, 3], targetSum = 5
Tree:
1
/ \
2 3
Output: false

Key phrase: "root-to-leaf path". The path must start at the root and end at a leaf. A leaf has no left or right child.

You can't stop at an internal node even if the sum matches. You must reach the bottom.

Trees are recursive structures. Each subtree is itself a tree. Use recursion (DFS) to walk from root to leaves.

At each node, subtract its value from the target. Pass the reduced target down. At a leaf, check if the remaining target is zero.

⚙ Knowledge Hub: Using Trees ⚙ Knowledge Hub: Recursion

Base case: if the node is null, return false (fell off the tree)
Subtract the current node's value from targetSum
If this node is a leaf (no left child, no right child), return whether targetSum == 0
Otherwise recurse on left and right children with the reduced target. Return true if either side returns true

def hasPathSum(root, targetSum):
    if not root:
        return False
    targetSum -= root.val
    if not root.left and not root.right:  # leaf
        return targetSum == 0
    return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    targetSum -= root->val;
    if (!root->left && !root->right)  // leaf
        return targetSum == 0;
    return hasPathSum(root->left, targetSum)
        || hasPathSum(root->right, targetSum);
}

public bool HasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    targetSum -= root.val;
    if (root.left == null && root.right == null)  // leaf
        return targetSum == 0;
    return HasPathSum(root.left, targetSum)
        || HasPathSum(root.right, targetSum);
}

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    targetSum -= root.val;
    if (root.left == null && root.right == null)  // leaf
        return targetSum == 0;
    return hasPathSum(root.left, targetSum)
        || hasPathSum(root.right, targetSum);
}

Path Sum II

LeetCode 113

Medium ▼

Source

LeetCode 113 - Path Sum II

Problem

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of node values.

Function Signature

pathSum(root: TreeNode, targetSum: int) -> list of lists

Examples

Input: root = [5 | 4, 8 | 11, null, 13, 4 | 7, 2, null, null, 5, 1], targetSum = 22
Tree:
      5
     / \
    4   8
   /   / \
  11  13  4
/  \     / \
7    2   5   1
Output: [[5,4,11,2], [5,8,4,5]]

Input: root = [1 | 2, 3], targetSum = 5
Tree:
1
/ \
2 3
Output: []

Same rules as Path Sum, but now you need all valid paths, not just whether one exists. You must collect the actual node values along each valid path.

There can be multiple valid paths or none at all.

Use DFS, same as Path Sum, but this time keep a list of the nodes you've visited so far. Each time you move to a child, add that node to the list. Each time you return from a child, remove the last item so the list is ready for the next branch.

When you reach a valid leaf, save a copy of that list to your results.

⚙ Knowledge Hub: Using Trees ⚙ Knowledge Hub: Recursion

Create a result list (collects valid paths) and a path list (current path being built)
DFS helper takes a node and the remaining sum
If node is null, return immediately
Append the node's value to path and subtract from remaining
If at a leaf and remaining is 0, append a copy of path to result
Recurse into left and right children
After both recursive calls, pop the last element from path (undo it before returning)

Copying the path is essential. If you just append the list reference, all entries in result will point to the same (eventually empty) list.

def pathSum(root, targetSum):
    result = []
    def dfs(node, remaining, path):
        if not node:
            return
        path.append(node.val)
        remaining -= node.val
        if not node.left and not node.right and remaining == 0:
            result.append(list(path))  # save a copy
        dfs(node.left, remaining, path)
        dfs(node.right, remaining, path)
        path.pop()  # backtrack
    dfs(root, targetSum, [])
    return result

vector<vector<int>> pathSum(TreeNode* root, int target) {
    vector<vector<int>> result;
    vector<int> path;
    function<void(TreeNode*,int)> dfs = [&](TreeNode* n, int rem) {
        if (!n) return;
        path.push_back(n->val);
        rem -= n->val;
        if (!n->left && !n->right && rem == 0)
            result.push_back(path);  // copy
        dfs(n->left, rem);
        dfs(n->right, rem);
        path.pop_back();  // backtrack
    };
    dfs(root, target);
    return result;
}

public IList<IList<int>> PathSum(TreeNode root, int target) {
    var result = new List<IList<int>>();
    var path = new List<int>();
    void Dfs(TreeNode n, int rem) {
        if (n == null) return;
        path.Add(n.val);
        rem -= n.val;
        if (n.left == null && n.right == null && rem == 0)
            result.Add(new List<int>(path));  // copy
        Dfs(n.left, rem);
        Dfs(n.right, rem);
        path.RemoveAt(path.Count - 1);  // backtrack
    }
    Dfs(root, target);
    return result;
}

public List<List<Integer>> pathSum(TreeNode root, int target) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, target, new ArrayList<>(), result);
    return result;
}
void dfs(TreeNode n, int rem, List<Integer> path,
        List<List<Integer>> result) {
    if (n == null) return;
    path.add(n.val);
    rem -= n.val;
    if (n.left == null && n.right == null && rem == 0)
        result.add(new ArrayList<>(path));  // copy
    dfs(n.left, rem, path, result);
    dfs(n.right, rem, path, result);
    path.remove(path.size() - 1);  // backtrack
}

Height of a Binary Tree

HackerRank

Easy ▼

Source

HackerRank - Height of a Binary Tree

Problem

Given the root of a binary tree, find its height. The height is the number of edges on the longest path from the root to a leaf. A tree with only a root node has height 0.

Function Signature

height(root: Node) -> int

Example

Tree:
      3
     / \
    2   5
   /   / \
  1   4   6
             \
              7
Array: [3 | 2, 5 | 1, null, 4, 6 | null, null, null, null, null, 7]
Output: 3 | Longest path: 3 -> 5 -> 6 -> 7 has 3 edges

Height counts edges, not nodes. A single node has height 0 (zero edges). An empty tree (null) has height -1.

You need the longest path from root down to any leaf.

The height of a node depends on the heights of its children. This is a natural recursive problem. Get the height of left subtree, get the height of right subtree, take the max, add 1.

⚙ Knowledge Hub: Using Trees ⚙ Knowledge Hub: Recursion

Base case: if node is null, return -1 (no edges below a missing node)
Recursively compute leftHeight = height(node.left)
Recursively compute rightHeight = height(node.right)
Return 1 + max(leftHeight, rightHeight)

Why -1 for null? A leaf node calls height on two null children, getting max(-1, -1) = -1, then returns 1 + (-1) = 0. That correctly gives a leaf height 0.

def height(root):
    if root is None:
        return -1
    return 1 + max(height(root.left), height(root.right))

int height(Node* root) {
    if (root == nullptr) return -1;
    return 1 + max(height(root->left), height(root->right));
}

public int Height(Node root) {
    if (root == null) return -1;
    return 1 + Math.Max(Height(root.left), Height(root.right));
}

public int height(Node root) {
    if (root == null) return -1;
    return 1 + Math.max(height(root.left), height(root.right));
}

Is Binary Search Tree

HackerRank

Medium ▼

Source

HackerRank - Is This a Binary Search Tree?

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST). In a BST, for every node: all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater. No duplicate values.

Function Signature

checkBST(root: Node) -> boolean

Examples

Valid BST:
      4
     / \
    2   6
   / \ / \
  1   3 5   7
Array: [4 | 2, 6 | 1, 3, 5, 7]
Output: true

Invalid BST:
      3
     / \
    2   5
   / \
  1   4
Array: [3 | 2, 5 | 1, 4, null, null]
Output: false | Explanation: 4 is in left subtree of 3 but 4 > 3

Common mistake: only checking if left.data < node.data < right.data for direct children. That's not enough.

Every node in the left subtree must be less than the root, not just the immediate left child. Same for the right side. The constraint flows down through the entire subtree.

Pass a valid range (min, max) down as you recurse. Each node must fall strictly within its allowed range. Going left tightens the upper bound. Going right tightens the lower bound.

⚙ Knowledge Hub: Using Trees ⚙ Knowledge Hub: Recursion

Create a helper function valid(node, low, high) that checks if a subtree is valid within range (low, high)
Start with low = -infinity, high = +infinity
Base case: if node is null, return true (an empty tree is a valid BST)
If node.data <= low or node.data >= high, return false
Recurse left with valid(node.left, low, node.data) (left children must be less than current)
Recurse right with valid(node.right, node.data, high) (right children must be greater than current)
Both must return true

def checkBST(root):
    def valid(node, low, high):
        if node is None:
            return True
        if node.data <= low or node.data >= high:
            return False
        return valid(node.left, low, node.data) \
           and valid(node.right, node.data, high)
    return valid(root, float('-inf'), float('inf'))

bool valid(Node* n, long low, long high) {
    if (!n) return true;
    if (n->data <= low || n->data >= high) return false;
    return valid(n->left, low, n->data)
        && valid(n->right, n->data, high);
}
bool checkBST(Node* root) {
    return valid(root, LONG_MIN, LONG_MAX);
}

bool Valid(Node n, long low, long high) {
    if (n == null) return true;
    if (n.data <= low || n.data >= high) return false;
    return Valid(n.left, low, n.data)
        && Valid(n.right, n.data, high);
}
bool CheckBST(Node root) {
    return Valid(root, long.MinValue, long.MaxValue);
}

boolean valid(Node n, long low, long high) {
    if (n == null) return true;
    if (n.data <= low || n.data >= high) return false;
    return valid(n.left, low, n.data)
        && valid(n.right, n.data, high);
}
boolean checkBST(Node root) {
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

In-order traversal visits: left subtree, then current node, then right subtree. For a valid BST, this produces values in strictly increasing order.

If at any point the current value is not greater than the previous one, the tree is not a valid BST.

Track the previously visited value, starting at negative infinity
Do an in-order traversal (recurse left, visit node, recurse right)
At each node, check: is node.data > prev? If not, return false
Update prev = node.data and continue
If the entire traversal completes without a violation, return true

def checkBST(root):
    prev = [float('-inf')]
    def inorder(node):
        if node is None:
            return True
        if not inorder(node.left):
            return False
        if node.data <= prev[0]:  # must be strictly increasing
            return False
        prev[0] = node.data
        return inorder(node.right)
    return inorder(root)

bool inorder(Node* n, long& prev) {
    if (!n) return true;
    if (!inorder(n->left, prev)) return false;
    if (n->data <= prev) return false;  // must increase
    prev = n->data;
    return inorder(n->right, prev);
}
bool checkBST(Node* root) {
    long prev = LONG_MIN;
    return inorder(root, prev);
}

long prev = long.MinValue;
bool Inorder(Node n) {
    if (n == null) return true;
    if (!Inorder(n.left)) return false;
    if (n.data <= prev) return false;  // must increase
    prev = n.data;
    return Inorder(n.right);
}
bool CheckBST(Node root) {
    prev = long.MinValue;
    return Inorder(root);
}

boolean checkBST(Node root) {
    long[] prev = {Long.MIN_VALUE};
    return inorder(root, prev);
}
boolean inorder(Node n, long[] prev) {
    if (n == null) return true;
    if (!inorder(n.left, prev)) return false;
    if (n.data <= prev[0]) return false;  // must increase
    prev[0] = n.data;
    return inorder(n.right, prev);
}

MODULE WEEK 5