# UVa 112

## Summary

Given a binary tree, determine if it is possible to traverse the tree to obtain a specific sum.

## Gotchas

• The input data could have negative values (the label in the nodes and also the integer to be found).
• As the description says, there could be empty trees.
• The path must end in a leaf node (of the form (integer () ()), not in a ().

## Implementations

It's easy to implement the tree (implicitly) if you think of parenthesis as a stack.

The input data is the result of a depth first search of the tree.

## Input

```22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10 (3
(2 (4 () () )
(8 () () ) )
(1 (6 () () )
(4 () () ) ) )
5 ()
0 ()
5 (5 () ())
5 ( 5 () () )
5 (1 (3 () ()) (4 () ()))
5 (18 ( -13 ( ) (  ))())
0 (1 ()(-2 () (1()()) ) )
2 (1 () (1 () (1 () () ) ) )
10 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )
10 (5 () (5 () (5 () (5 ( 3 () () ) (4 () () ) ) ) ) )
20 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )
```

```yes
no
yes
no
no
yes
yes
yes
yes
yes
no
no
no
no
```

## References

1. Reference 1

Categories here, use the form [[Category:UVa Online Judge|112]] [[Category: Category Name]], see Categories for a list