Downward Chains With a Given Total

Medium

You are given the root root of a binary tree and an integer total. Count the *downward chains* in the tree whose node values add up to total. A downward chain is one or more nodes where each next node is a child of the previous one. A chain may start and end anywhere: it need not begin at the root or finish at a leaf. Two chains are different if they consist of different nodes.

Example 1

root=tree_node([2, 3, -1, 1, None, 4]), total=3 → 2

Two chains sum to 3: the single node 3 and the chain -1 → 4. By contrast, 2 → -1 only gives 1.

Example 2

root=tree_node([0, 0, None, 0]), total=0 → 6

Three one-node chains, two two-node chains and one three-node chain: 6 in total.

Example 3

root=tree_node([5]), total=-5 → 0

Constraints

The tree has 0 to 10⁵ nodes
-10⁹ ≤ node value ≤ 10⁹
-1000 ≤ total ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium All Leaf Paths With a Given Total Medium Tree Into a Right Chain Medium Digit Branch Totals Medium

Input

root=tree_node([2, 3, -1, 1, None, 4]), total=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.