Recover Binary Search Tree, is a LeetCode problem from Tree subdomain. In this post we will see how we can solve this challenge in Swift

## Problem Description

You can find the full details of the problem Recover Binary Search Tree at LeetCode

## Solution

The key is to construct the connection between child & parent

1. If cur.left == nil:

• Output cur.val

• Set cur = cur.right

2. If cur.left != nil:

• Find the precursor of cur, precursor

i. If precursor.right == nil:

• Set precursor.right = cur

• Set cur = cur.left

ii. If precursor.right != nil (which means precursor.right === cur):

• Set precursor.right = nil (Recover the structure of original tree)

• Output cur.val

• Set cur = cur.right

3. Repeat 1) & 2) until cur == nil

Time Complexity: O(n), Space Complexity: O(1)

Definition for a binary tree node.

public class TreeNode {

``````public var val: Int

public var left: TreeNode?

public var right: TreeNode?

public init(_ val: Int) {

self.val = val

self.left = nil

self.right = nil

}``````

}

Please check the main.swift snippet for the solution.

This solution originally posted at: Github by @soapyigu