Search⌘ K
AI Features

Invert Binary Tree

Explore how to invert a binary tree by applying depth-first search techniques in Swift. Understand the method to swap subtrees, analyze time and space complexity, and gain practical experience useful for coding interviews involving tree operations.

Description

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

Let’s look at an example below:

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:

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
...