หาคู่ 숫자ที่ผลรวมเท่ากับเป้าหมายใน Balanced BST (Java)

โจทย์

กำหนด Balanced BST และ target sum หาว่ามีคู่โหนดไหนที่ผลรวม = target หรือไม่ Time complexity O(n), Space O(log n) ห้ามแก้ไข BST

วิธีแก้: Inorder Traversal + Two Pointers

1. Inorder traversal ของ BST ให้ sorted array
2. ใช้ two pointers (หนึ่งหัว, หนึ่งท้าย) หาคู่ที่ผลรวม = target
3. Time: O(n) สำหรับ traversal + O(n) สำหรับ two pointers = O(n)
4. Space: O(n) สำหรับ array (แต่อยากได้ O(log n) ต้องทำแบบ iterative + stack)

ตัวอย่างโค้ด (เวอร์ชัน O(n) space)

import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int d) { data = d; left = right = null; }
}

public class BinarySearchTree {
    Node root;
    
    void insert(int key) { root = insertRec(root, key); }
    
    Node insertRec(Node root, int data) {
        if (root == null) return new Node(data);
        if (data < root.data) root.left = insertRec(root.left, data);
        else if (data > root.data) root.right = insertRec(root.right, data);
        return root;
    }
    
    // Inorder traversal เก็บใน ArrayList
    ArrayList treeToList(Node node, ArrayList list) {
        if (node == null) return list;
        treeToList(node.left, list);
        list.add(node.data);
        treeToList(node.right, list);
        return list;
    }
    
    boolean isPairPresent(Node node, int target) {
        ArrayList list = treeToList(node, new ArrayList<>());
        int left = 0, right = list.size() - 1;
        
        while (left < right) {
            int sum = list.get(left) + list.get(right);
            if (sum == target) {
                System.out.println("Pair Found: " + list.get(left) + " + " + list.get(right) + " = " + target);
                return true;
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println("No such values are found!");
        return false;
    }
    
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(16); tree.insert(11); tree.insert(21);
        tree.insert(9); tree.insert(13); tree.insert(17); tree.insert(26);
        tree.isPairPresent(tree.root, 34);
    }
}

ผลลัพธ์

Pair Found: 13 + 21 = 34

วิธี O(log n) Space (Advanced)

ใช้ 2 iterator แบบ inorder (normal + reverse) พร้อมกัน แต่ละ iterator ใช้ stack สูงสุด O(h) = O(log n) สำหรับ balanced BST