Recover Binary Search Tree — LeetCode 99 Python Solution
MediumTreeDepth-First SearchBinary Search TreeBinary Tree
- Problem
- #99
- Pattern
- Tree Traversal
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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
- 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.
Python solution
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def dfs(root):
if root is None:
return
nonlocal prev, first, second
dfs(root.left)
if prev and prev.val > root.val:
if first is None:
first = prev
second = root
prev = root
dfs(root.right)
prev = first = second = None
dfs(root)
first.val, second.val = second.val, first.valComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 99. Recover Binary Search Tree is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 99. Recover Binary Search Tree?
- LeetCode 99. Recover Binary Search Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 99. Recover Binary Search Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 99. Recover Binary Search Tree?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 99. Recover Binary Search Tree cover?
- LeetCode 99. Recover Binary Search Tree is tagged Tree, Depth-First Search, Binary Search Tree and Binary Tree on LeetCode.