# LeetCode – 101. Symmetric Tree

## Recursive version:

func isSymmetric(_ root: TreeNode?) -> Bool {
return root == nil || helper(root?.left, root?.right)
}

func helper(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
if left == nil && right == nil {
return true
} else if left?.val != right?.val {
return false
} else {
return helper(left?.left, right?.right) && helper(left?.right, right?.left)
}
}

// Test cases:
// nil
// [1, 2, 2]
// [1, 2, 2, 3, 4, 4, 3]
func isSymmetric(_ root: TreeNode?) -> Bool {
guard let root = root else { return true }
var arrLeft = [Int]()
var arrRight = [Int]()
traverseLeftTree(root.left, &arrLeft)
traverseRightTree(root.right, &arrRight)
return arrLeft == arrRight
}

func traverseLeftTree(_ root: TreeNode?, _ arr: inout [Int]) {
guard let root = root else {
arr.append(0)
return
}
arr.append(root.val)
traverseLeftTree(root.left, &arr)
traverseLeftTree(root.right, &arr)
}

func traverseRightTree(_ root: TreeNode?, _ arr: inout [Int]) {
guard let root = root else {
arr.append(0)
return
}
arr.append(root.val)
traverseRightTree(root.right, &arr)
traverseRightTree(root.left, &arr)
}

## Iterative version

func isSymmetric(_ root: TreeNode?) -> Bool {
guard let root = root else { return true }
var stackLeft: [TreeNode?] = [root.left]
var stackRight: [TreeNode?] = [root.right]
while !stackLeft.isEmpty && !stackRight.isEmpty {
let left = stackLeft.removeLast()
let right = stackRight.removeLast()
if left == nil && right == nil {
// do nothing
} else if left?.val != right?.val {
return false
} else {
stackLeft.append(left?.left)
stackLeft.append(left?.right)

stackRight.append(right?.right)
stackRight.append(right?.left)
}
}
return stackLeft.isEmpty && stackRight.isEmpty
}