UVa 112

From Algorithmist

Contents 1 112 - Tree Summing 2 Summary 3 Explanation 4 Gotchas 5 Notes 6 Implementations 7 Optimizations 8 Input 9 Output 10 References

[edit] 112 - Tree Summing

• UVA 112
• PKU 1145
• SWJTU 1420 (uses different input format, but same type of problem.)

[edit] Summary

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

[edit] Explanation

[edit] 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.

[edit] Notes

[edit] 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.

[edit] Optimizations

[edit] 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 () () ) ) ) ) )

[edit] Output

yes
no
yes
no
no
yes
yes
yes
yes
yes
no
no
no
no

[edit] References

1. Reference 1

Categories here, use the form [[Category: Category Name]], see Categories for a list