CODEWITHSUNDEEP
haskellbinary-search-tree
Gloria95
Gloria95

Reputation: 139

Post order for a general tree? (Haskell)

I asked this question earlier, but I did not know the difference between a rose tree and general tree. Now I know that the data structure is slightly different.

data GTree a = Leaf a | Branch [GTree a]

I would like to write a postorderG function that would give me a list with all the elements of Gtree in postorder.

I know how to do it for a binary tree. 

data BTree a = Nil | Node a (BTree a) (BTree a) 

postOrder :: BTree a -> [a]
postOrder Nil = []
postOrder (Node x lt rt) = (postOrder lt) ++ (postOrder rt) ++ [x]

Upvotes: 1

Views: 556

Answers (1)

Code-Apprentice
Code-Apprentice

Reputation: 83527

A GTree just has as many branches as you wish, not just two. The concept for post order traversal is still the same: visit all branches before visiting the current node. You can do this either with explicit recursion on the list of branches or with map or reduce.

Upvotes: 2

Related Questions