# Problem 56

We call a binary tree symmetric if you can draw a vertical line through the root node and the right subtree is the mirror image of the left subtree. Write a function to check if a binary tree is structurally symmetric (ignore the node values).

## Example

``````tree1 =
Node 1
(Node 2
(Node 3 Empty Empty)
(Node 4
Empty
(Node 5 Empty Empty)))
(Node 6
(Node 7 Empty Empty)
(Node 8
(Node 9 Empty Empty)
Empty)))

isSymmetric tree1 == True
``````

## Unit Test

``````import Html
import List

type Tree a
= Empty
| Node a (Tree a) (Tree a)

isSymmetric : Tree a -> Bool
isSymmetric tree =
False

main : Html.Html a
main =
Html.text
(if (test) then
else
"Your implementation failed at least one test."
)

test : Bool
test =
List.all ((==) True)
[ isSymmetric tree1
, isSymmetric (Node '1' Empty (Node '2' Empty Empty)) == False
, isSymmetric (Node '1' (Node '2' Empty Empty) (Node '3' Empty (Node '4' Empty Empty))) == False
, isSymmetric Empty
, isSymmetric (balancedTree 3)
, isSymmetric (balancedTree 4) == False
, isSymmetric (balancedTree 6) == False
, isSymmetric (balancedTree 7)
, isSymmetric (balancedTree 15)
, isSymmetric (balancedTree 31)
, isSymmetric (balancedTree 32) == False
]

tree1 =
Node 1
(Node 2
(Node 3 Empty Empty)
(Node 4
Empty
(Node 5 Empty Empty)))
(Node 6
(Node 8
(Node 9 Empty Empty)
Empty)
(Node 7 Empty Empty))

balancedTree : Int -> Tree Char
balancedTree n =
List.foldl (addBalancedNode) Empty <| List.repeat n 'x'

addBalancedNode : a -> Tree a -> Tree a
case tree of
Empty ->
Node v Empty Empty

Node v_ left right ->
if count left > count right then
Node v_ left (addBalancedNode v right)
else
Node v_ (addBalancedNode v left) right

-- count number of Nodes in a Tree
count : Tree a -> Int
count tree =
case tree of
Empty -> 0

Node n left right ->
1 + (count left) + (count right)
``````

## Hint

1. Look in the mirror (recursively).