Recover Binary Search Tree
Updated
Problem statement
You are given the root of a binary search tree in which the values of exactly two nodes were swapped by mistake. Restore the binary search tree without changing its structure.
Return the same root after you fix the tree. The tests read the fixed tree to check it.
Function
recoverTree(root: TreeNode) → TreeNodeExamples
Example 1
root = [1,3,null,null,2]return = [3,1,null,null,2]Moved or new
The value 3 cannot be the left child of 1 in a valid binary search tree. Swapping 1 and 3 restores the ordering.
Example 2
root = [3,1,4,null,null,2]return = [2,1,4,null,null,3]Moved or new
The inorder sequence is [1,3,2,4]. Swapping the misplaced values 3 and 2 makes it increasing.
Example 3
root = [2,3,1]return = [2,1,3]Moved or new
The two child values are reversed. Swapping them preserves the three-node structure and restores the tree.
Constraints
- The tree contains between
2and1000nodes. -2^31 <= Node.val <= 2^31 - 1- The input was a valid binary search tree before exactly two node values were exchanged.
More Globalization Partners Onsite Interview questions
Similar questions at other companies
- Merge N-Ary Trees by KeyLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
- Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEWCursor interview questions
- Aggregate Machine TopologyOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Recursive Display SortFigma · PHONE SCREEN · ONSITE INTERVIEWFigma interview questions
- Vertical Order Traversal of a Binary TreeBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Vertical Order Traversal of a Binary TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions
- Find All Paths for a Name in a File SystemThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Build a Trace ForestDatadog · PHONE SCREENDatadog interview questions
- Analyze Underpaid Managers in a Salary TreeGoogle · PHONE SCREENGoogle interview questions
- Vertical Tree Traversal with Value TiesMeta · PHONE SCREENMeta interview questions