1 minute read

99. Recover Binary Search Tree

Difficulty: Medium

Related Topics: Tree, BFS/DFS, Binary Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Example 1:

Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2] Output: [2,1,4,null,null,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

First Attempt:

Code:

head = root.val
        temp = [root]
        def swap(r1, r2):
            r1.val, r2.val = r2.val, r1.val

        def traverse(root):
            prev = root.val
            stack = []
            stack.append(root)
            while stack:
                curr = stack.pop()
                if curr.right:
                    if curr.right.val < prev or curr.right.val < head:
                        temp.append(curr.right)
                    stack.append(curr.right)
                if curr.left:
                    if curr.left.val > prev or curr.left.val > head:
                        temp.append(curr.left)
                    stack.append(curr.left)
                prev = curr.val

            if len(temp) == 2:
                swap(temp[0], temp[1])
            elif len(temp) == 3:
                swap(temp[1], temp[2])

        traverse(root)

Feedbacks:

I tried to solve this problem using dfs iterative. I stored invalid values to the list and after the traverse finish, I tried to swap between the invalid values. It passed 125 testcases among 1200 testcases. There were some logical issues in my code.

Second Attempt:

Code:

temp=[]
        def dfs(root):
            if not root: return
            else:
                dfs(root.left)
                temp.append(root.val)
                dfs(root.right)
            print("temp",temp)
        count=0
        def replace(root,temp):
            if not root: return
            else:
                replace(root.left, temp)
                root.val = temp[0]
                temp.pop(0)
                replace(root.right, temp)
        
        dfs(root)
        temp = sorted(temp)
        replace(root,temp)

Feedbacks:

Traverse through the tree by inorder traversal and store the values to the list. After sorting the list, I replace the values in list to each corresponding place in the tree.

You may also enjoy