Why Two Sum in BST in DSA Go?

The Big Idea

What if you could find two numbers adding to your target in a tree without checking every pair?

The Scenario

Imagine you have a big family photo album sorted by year. You want to find two photos whose years add up to a special number, but you have to flip through every page manually.

The Problem

Flipping through every page one by one is slow and tiring. You might miss some photos or check the same page twice. It's easy to get lost or confused.

The Solution

Using a smart way to check pairs of photos by using the album's sorted order helps you find the two photos quickly without flipping every page multiple times.

Before vs After

✗ Before

func findTwoSumInArray(arr []int, target int) bool {
  for i := 0; i < len(arr); i++ {
    for j := i + 1; j < len(arr); j++ {
      if arr[i]+arr[j] == target {
        return true
      }
    }
  }
  return false
}

✓ After

func findTwoSumInBST(root *TreeNode, target int) bool {
  vals := inorder(root)
  i, j := 0, len(vals)-1
  for i < j {
    sum := vals[i] + vals[j]
    if sum == target {
      return true
    } else if sum < target {
      i++
    } else {
      j--
    }
  }
  return false
}

What It Enables

This lets you quickly find two numbers in a sorted tree that add up to a target, saving time and effort.

Real Life Example

Finding two expenses in your sorted bank statement that add up to a specific budget limit without checking every possible pair.

Key Takeaways

Manual checking is slow and error-prone.

Using BST properties speeds up finding pairs.

Two-pointer technique on BST traversal arrays is efficient.