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. Continue comparing every two consecutive pair to find the last item that’s not in its place. Let’s name this s (for second). As soon as you find the 2nd item, then you can stop searching.
  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]
       ↑__↑     ↑__↑
   first-pair  second-pair
       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 sBadVal: Int? 
var didFindFirstNodeThatNeedsSwapping = false
for i in 0..<tree.count {
    if let next = tree[safe:i + 1], next.val < tree[i].val{
        if didFindFirstNodeThatNeedsSwapping == false { 
            fBadVal = tree[i].val
            didFindFirstNodeThatNeedsSwapping = true
        }
        
        sBadVal = tree[i + 1].val
    }
}
The swapping nodes happen between the first node of the first bad pair (8) && the second node of the second bad pair (3).

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)

1, 2, 8, 4, 7, 6 , 3


                4
           /         \
        2               7
      /   \           /   \   
    1       8       6       3

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 fBadVal: Int? 
        var sBadVal: Int? 
        var didFindFirstNodeThatNeedsSwapping = false
        for i in 0..<tree.count {
            if let next = tree[safe:i + 1], next.val < tree[i].val{
                if didFindFirstNodeThatNeedsSwapping == false { 
                    fBadVal = tree[i].val
                    didFindFirstNodeThatNeedsSwapping = true
                }
                
                sBadVal = tree[i + 1].val
            }
        }
        print(fBadVal, sBadVal)
        
        // traverse again & swap elements
        inOrder(root) { node in 
            node.map { node in
                if node.val == fBadVal  {
                    node.val = sBadVal!
                } else if node.val == sBadVal { 
                    node.val = fBadVal!
                }
            }              
        }

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