Invert Binary Tree

Understand and solve the interview question "Invert Binary Tree".

Description

In this lesson, your task is to invert a given binary tree, T.

Let’s look at an example below:

main.swift
TreeNode.swift
import Swift
func invertTree(root: TreeNode?) -> TreeNode? {
return root
}
Invert binary tree exercise

Solution

We can solve this problem using depth-first search (DFS).

The inverse of an empty tree is the empty tree. To invert tree T with root and subtrees left and right, we keep root the same and invert the right and left subtrees.

Let’s review the implementation below:

main.swift
TreeNode.swift
import Swift
func invertTree(root: TreeNode?) -> TreeNode? {
if root == nil {
return root
}
let right: TreeNode? = invertTree(root: root!.right)
let left: TreeNode? = invertTree(root: root!.left)
root!.left = right
root!.right = left
return root
}
func helper(node: TreeNode?, level: Int, levels: inout [[Int]]) {
// start the current level
if levels.count == level {
levels.append([])
}
// fulfil the current level
levels[level].append(node!.val)
// process child nodes for the next level
if node!.left != nil {
helper(node: node!.left, level: level + 1, levels: &levels)
}
if node!.right != nil {
helper(node: node!.right, level: level + 1, levels: &levels)
}
}
func to_string(vec: [[Int]]) -> String{
var str = "["
var i: Int = 0
var j: Int = 0
while i < vec.count {
str += "["
j = 0
while j < vec[i].count {
str += String(vec[i][j])
if j + 1 < vec[i].count {
str += ", "
}
j += 1
}
str += "]"
if i + 1 < vec.count {
str += ", "
}
i += 1
}
str += "]"
return str
}
func levelOrder(root: TreeNode?) -> [[Int]] {
var levels: [[Int]] = []
if root == nil { return levels }
helper(node: root, level: 0, levels: &levels)
return levels
}
func Print(root: TreeNode?){
let vec: [[Int]] = levelOrder(root: root)
print(to_string(vec: vec))
}
let root: TreeNode = TreeNode(x: 1)
root.left = TreeNode(x: 2)
root.right = TreeNode(x: 3)
root.left!.left = TreeNode(x: 4)
root.left!.right = TreeNode(x: 5)
root.right!.left = TreeNode(x: 6)
root.right!.right = TreeNode(x: 7)
let res: TreeNode? = invertTree(root: root)
Print(root: root)
Invert binary tree solution

Complexity measures

Time Complexity Space Complexity
...