How to test if my implementation of tree/graph data structures are correct?
Identify the representation invariants.  Add assert statements to check that the representation invariant holds (sometimes called a repOK function).  Use random testing to generate millions of test cases, and check that no assert ever fires.

Build a reference implementation of the abstract data type that implements all of the methods, but instead of using your data structure, implements the same semantics using some known-good data structure (e.g., a simple list or something).  Use random testing to generate millions of test cases, and check that in every case your implementation produces the same results as the reference implementation.

This isn't perfect but it'll probably be pretty good.