The word "tree" is a not a taxonomic classification, but a human perceptual clustering based on form and size. The word "fish" has a similar problem, covering a vast collection of taxa, some of which are less closely related to one another than they are to us.
Becoming tree-like often has a strong evolutionary value, because plants ...
I don't know the exact species, but this is likely to be a Hakea species. These are a widespread genus of plants in Australia, with a hard persistent woody seed that splits open after heating (usually fire) or plant death (as in your case) to release two seeds.
You can see some photos of seed pods at Project Noah, showing the classic bifurcate seed pod.