Binary Tree Path Sums

ITU data structures coursework, 2019. Restored in 2026: input checks, no size limit, a bug fix, stdin support, tests, CI. Original code: tag original-2019.

Run it online (Compiler Explorer, runs examples/figure-2.txt as stdin)

The task

The first line of the input holds the values of a binary tree. They fill a complete tree level by level, left to right. Node 1 is the root, and node k has the children 2k and 2k+1:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

The second line holds the target.

Find one path in the left subtree of the root and one in the right subtree. A path starts at the root, goes down into that subtree, and may end at any node, not only at a leaf. The values on the path add up to the target. The root alone is in neither subtree, so a path has at least one node below the root.

If a subtree has several such paths, the first one found in preorder wins (a node comes before its children, the left child before the right one).

The program prints two lines, left first: Path Found: v1 v2 ... or No Path Found.

Example 1, examples/figure-1.txt (10 13 28 25 15 45 53, target 38):

          10
        /    \
      13      28
     /  \    /  \
   25    15 45    53

Path Found: 10 13 15      (10 + 13 + 15 = 38)
Path Found: 10 28         (10 + 28 = 38)

Example 2, examples/figure-2.txt (10 13 28 10 15 45 53 5, target 38). The left path goes down to node 8:

            10
          /    \
       13        28
      /  \      /  \
    10    15   45    53
   /
  5

Path Found: 10 13 10 5    (10 + 13 + 10 + 5 = 38)
Path Found: 10 28         (10 + 28 = 38)

Input rules

• Line 1: one or more whole numbers in the int range, separated by spaces or tabs.
• Line 2: exactly one whole number in the int range.
• Nothing but whitespace after line 2. A missing final newline and \r\n line endings are fine.

If a rule is broken, the program prints error: line N: <what is wrong> on stderr and exits with status 1.

Build and run

make                                  # builds ./b_tree
./b_tree examples/figure-1.txt        # read a file
./b_tree < examples/figure-1.txt      # read stdin
make test                             # build and run the tests

With more than one argument the program prints a usage line and exits with status 2.

How it works

The tree is complete, so a node's place follows from its number: the parent of node k is node k / 2, and k is a left child if it is even. The program keeps the nodes in a vector indexed by node number. That way adding a node needs no search, and the tree has no size limit.

The search is a preorder walk of each subtree of the root. It carries the running sum (in long long), the text of the path and the side (left or right). The side is set by the root's child and does not change below it. When the sum equals the target, the path is kept if its side has no path yet.

Changes in 2026

• Fixed: a target equal to the root's value printed the root alone as the left path. A path now needs at least one node below the root.
• Removed: the hidden limit of 2047 nodes (the old code wrote past a fixed array above it).

License

MIT, see LICENSE.