Answer: Nutanix SWE OA (2023) | Binary Search Tree Validation and Tree Recovery Intervie

Approach A Binary Search Tree follows: Left Subtree < Root < Right Subtree When performing an inorder traversal of a BST, the values should appear in: Sorted Ascending Order If two nodes are swapped, this sorted order gets violated. Key Observation Consider the correct inorder traversal: 1 2 3 4 5 After swapping two nodes: 1 4 3 2 5 Notice the violations: 4 > 3 3 > 2 The misplaced nodes are: First Node = 4 Second Node = ...