Path Sum Root to Leaf in Binary Tree in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does "Path Sum Root to Leaf" mean in a binary tree?

It means finding if there is a path from the root node down to any leaf node where the sum of all node values equals a given number.

beginner

What is a leaf node in a binary tree?

A leaf node is a node that has no children, meaning both its left and right pointers are null.

intermediate

In the path sum problem, why do we subtract the current node's value from the target sum as we go down the tree?

Because we want to check if the remaining sum can be found in the subtree. Subtracting the current node's value updates the target for the next nodes.

intermediate

What is the base case when using recursion to solve the path sum problem?

When the current node is null, return false because no path exists. When the current node is a leaf, check if its value equals the remaining sum.

beginner

How do you know if a path sum exists in the binary tree?

If any path from root to leaf has node values adding up exactly to the target sum, return true; otherwise, false.

What should you check first when solving the path sum problem recursively?

A If the tree is balanced

B If the current node has two children

C If the current node is null

D If the sum is zero

The first check is if the current node is null, which means no path exists here.

When do you return true in the path sum problem?

A When the current node is a leaf and its value equals the remaining sum

B When the current node has at least one child

C When the sum is greater than zero

D When the root is null

You return true only if you reach a leaf node and the remaining sum equals that leaf's value.

What is the main technique used to solve the path sum problem?

A Recursion

B Sorting

C Dynamic programming

D Hashing

Recursion is used to explore all paths from root to leaves.

If the target sum is 22 and the root node value is 5, what is the new sum to check in the children?

A 5

B 27

C 22

D 17

Subtract the root value 5 from 22, so the new sum to check is 17.

Which nodes do you consider when checking for path sum?

A Only root nodes

B All nodes from root to leaf

C Only leaf nodes

D Only nodes with two children

You consider all nodes along the path from root to leaf.

Explain how recursion helps to find if a path sum exists from root to leaf in a binary tree.

Think about how you reduce the problem size at each step.

Describe the steps to check if a binary tree has a root-to-leaf path with a given sum.

Imagine walking down the tree and keeping track of the remaining sum.