This is No.99 in LeetCode. Here are approaches to this problem: Approach 1: Sort an Almost Sorted Array Where Two Elements Are Swapped Algorithm Here is the algorithm: Construct inorder traversal of the tree. It should be an almost sorted list where only two elements are swapped. Identify two swapped elements x and y in …
Tree Traversals
Inorder Traversal Algorithm Inorder(tree) Traverse the left subtree, i.e., call Inorder(left-subtree) Visit the root. Traverse the right subtree, i.e., call Inorder(right-subtree) Preorder Traversal Algorithm Preorder(tree) Visit the root. Traverse the left subtree, i.e., call Preorder(left-subtree) Traverse the right subtree, i.e., call Preorder(right-subtree) Postorder Traversal Algorithm Postorder(tree) Traverse the left subtree, i.e., call Postorder(left-subtree) Traverse the …