## Question:#

You have a binary tree. But only two of its elements have been swapped. This makes it a faulty binary tree. The challenge is to swap those two elements. And fix the tree.

## Solution#

I knew I had to traverse it. But then what?

With a little help from reading online, I realized I should traverse it, and store the values into an array. Then you just loop the array and find the bad indexes.

Here’s the tricky part:

Suppose your array is something like:

``````[1, 2, 4, 3, 6, 7, 8]
``````

You loop and find out 4 is in a bad spot. You swap it with 3. And your tree is fixed.

However if your array ends up like this:

``````[1, 2, 8, 4, 6, 7, 3]
``````

You loop and find out 8, is in a bad spot. You swap it with 4 and up with:

``````[1, 2, 4, 8, 6, 7, 3]
``````

but that’s still incorrect.

So once you have the array built, what you need to do is:

1. Find the first item that not in its place. Let’s name this `f` (for first).
2. Find the last item that’s not in its place. Let’s name this `s` (for second).
3. Swap those two items.

To show you step two visually:

``````[1, 2, 8, 4, 6, 7, 3]
↑  ↑
❗️ ❗️
f  s

[1, 2, 8, 4, 6, 7, 3]
↑  ↑     ↑  ↑
❗️ ❗️   ❗️ ❗️
f  ←⎯⎯⎯→  s

Perform swap between `f` and `s`:
[1, 2, 3, 4, 6, 7, 8]
``````

The heart of all the code would be:

``````var fBadVal: Int?
var didSwapFirst = false
for i in 0..<tree.count {
if let next = tree[safe:i + 1], next.val < tree[i].val{
if didSwapFirst == false {
didSwapFirst = true
}

}
}
``````

### Setup of bad Binary tree:#

``````class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}

var one = TreeNode(1, nil, nil)
var eight = TreeNode(8, nil, nil) // bad position
var six = TreeNode(6, nil, nil)
var three = TreeNode(3, nil, nil) // bad position

var two = TreeNode(2,one, eight)
var seven = TreeNode(7, six, three)

// root node
var four = TreeNode(4, two, seven)

``````

### Actual code:#

``````class TreeFixer {
var tree: [TreeNode] = []

func recoverTree(_ root: TreeNode?) {
// traverse the tree
inOrder(root) { node in
node.map {tree.append(\$0)}
}
print(tree.map {\$0.val})

// find the elements where they're not matching...
var didSwapFirst = false
for i in 0..<tree.count {
if let next = tree[safe:i + 1], next.val < tree[i].val{
if didSwapFirst == false {
didSwapFirst = true
}

}
}

// traverse again & swap elements
inOrder(root) { node in
node.map { node in
} else if node.val == sBadVal {
}
}
}

// print new tree, so we can validate our work...
print("SORTED TREE: InOrderTraversal")
inOrder(root) { node in
print(node?.val)
}

}

// Traverse tree and return a block handler for each node.
func inOrder(_ root: TreeNode?, nodeHandler: (TreeNode?) -> ()) {
if let left = root?.left {
inOrder(left) { node in
nodeHandler(node)
}

}
nodeHandler(root)

if let right = root?.right {
inOrder(right) { node in
nodeHandler(node)
}
}
}
}

extension Array {
public subscript(safe index: Int) -> Element? {
guard index >= 0, index < endIndex else {
return nil
}

return self[index]
}
}

let fixer = TreeFixer()
fixer.recoverTree(four)
``````

## Time Complexity#

• Traversing is `O(n)`.
• Appending to the array is `O(1)`.
• Traversing the array is `O(n)`.
• swapping in the tree is `O(n)`.

Given that they’re not nested to total Time complexity is `O(n)`

## Space Complexity#

`O(n)` because you need an array.

## Summary:#

• Often translating a tree into an array can be helpful.
• Using an `inOrder` method that takes a handler block can be helpful.
• Using a safe subscript for the array…something that Swift doesn’t have can be helpful.
• main trick was to continuously look for 2nd index.