Binary Search Tree Node Swap

Introduction

• Discussed a problem: Two nodes in a Binary Search Tree (BST) are swapped.
• Goal: Identify and correct the swapped nodes.

Problem Explanation

• Example Tree:
  • Nodes: 5, 7, 6, 8, 3, 4, 2, 1
  • Swapped Nodes: 2 and 7
• Corrected order after swap: 1, 2, 3, 4, 5, 6, 7, 8

In Order Traversal

• In a correct BST, in-order traversal results in a sorted array.
• Problem approach: Identify deviations in the sorted order caused by the swap.

Steps to Solve

1. Perform in-order traversal.
2. Identify two violations where the order is incorrect.
3. Set pointers for first and second violations.
4. Swap these nodes to fix the tree.

Detailed Steps

1. **Initialization:
   • Variables: firstViolation = null, secondViolation = null
2. **In-Order Traversal:
   • Traverse the tree left, current, then right.
   • On encountering a node, if it violates the sorted order:
     • First Violation: firstViolation = previous node.
     • Second Violation: secondViolation = current node.
3. Swap Nodes:
   • Swap the values of the first and second violation nodes.

Implementation in Java

• Class Definition: Node

  class Node {
      int value;
      Node left;
      Node right;
      public Node(int val) {
          this.value = val;
      }
  }
  

• Solution Class:

  public class TwoNodeSwap {
      Node first = null;
      Node second = null;
      Node previous = null;
  
      public void helper(Node root) {
          inOrderTraversal(root);
          int temp = first.value;
          first.value = second.value;
          second.value = temp;
      }
  
      private void inOrderTraversal(Node node) {
          if (node == null) return;
  
          inOrderTraversal(node.left);
          if (previous != null && previous.value > node.value) {
              if (first == null) first = previous;
              second = node;
          }
          previous = node;
          inOrderTraversal(node.right);
      }
  }
  

Complexity Analysis

• Time Complexity: O(n) - Each node is visited once.
• Space Complexity: O(h) - Due to recursion stack, where h is the height of the tree.

Summary and Conclusion

• We identified the problem, discussed the approach using in-order traversal, set up correct pointers for violations, and fixed the tree by swapping the nodes.
• Example code provided with explanations for each step.
• Encouragement to practice and apply the concept.

Closing Remarks

• Holidays Greetings: Wished Happy New Year and informed about upcoming concepts in the boot camp.