ข้อ 41 · LC700 Search in a Binary Search Tree (ค้นหาใน BST) 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

ใช้กฎ left < node < right เดินลงต้นไม้ ตัดครึ่งที่ไม่เกี่ยวทิ้งทุกก้าว หาเจอใน O(h)

โจทย์ (LC700): กำหนด root ของ binary search tree (BST) และเลขจำนวนเต็ม val ให้หา node ใน BST ที่มีค่าเท่ากับ val แล้ว return subtree ที่มี node นั้นเป็น root (คืนตัว node นั้นทั้งก้อน รวม child ทั้งหลายของมัน) ถ้าไม่มี node แบบนั้นให้ return null

Example 1

Input:: root = [4,2,7,1,3], val = 2
Output:: [2,1,3]
Explanation:: คืน subtree ที่ root คือ node 2 ซึ่งมี child ซ้าย 1 และ child ขวา 3

Example 2

Input:: root = [4,2,7,1,3], val = 5
Output:: []
Explanation:: ไม่มีค่า 5 อยู่ใน BST นี้เลย จึง return null

Constraints (ข้อจำกัด)

จำนวน node อยู่ระหว่าง 1 ถึง 5000
1 <= Node.val <= 10^7
1 <= val <= 10^7
root เป็น BST จริง (รับประกันโดยโจทย์)

แนวทาง — ต้องใช้อะไร & คิดยังไง

data structure ที่ใช้คือ BST เอง และเทคนิคคือ traverse (เดินไล่) ลง tree (ต้นไม้) โดยอาศัยกฎ left < node < right เลือกใช้วิธีนี้เพราะโจทย์การันตีว่าค่าถูก sort (เรียง) ไว้แล้ว เราจึงไม่ต้องเสียแรงดูทุก node

วิธีช้าแบบ brute force คือ iterate (วน) ดูทุก node ใน tree (traversal ธรรมดา) จนกว่าจะเจอค่า ซึ่งเป็น O(n) แต่มันไม่ใช้ประโยชน์จากการที่ค่า sort อยู่แล้วเลย ทั้งที่ทุกครั้งที่ compare (เทียบ) ค่าเราตัดครึ่งของ tree ที่เป็นไปไม่ได้ทิ้งได้ทันที นั่นนำไปสู่วิธีเดินลงข้างเดียวที่เร็วกว่ามาก

ตั้ง pointer (ตัวชี้) node ไว้ที่ root
ถ้า node ยังไม่หลุดขอบ (ไม่ใช่ None) ให้ compare ค่า
ถ้า val เท่ากับค่า node ปัจจุบัน เจอแล้ว คืน node นั้นทั้งก้อน
ถ้า val น้อยกว่า ให้ขยับ node ไป child ซ้าย (ค่าเล็กกว่าอยู่ฝั่งซ้ายเสมอ)
ถ้า val มากกว่า ให้ขยับ node ไป child ขวา
ถ้าเดินจนหลุดขอบ tree (node เป็น None) แปลว่าไม่มี คืน None

จุดพลาดที่พบบ่อย

ลืมคืน None ตอนเดินจนตกขอบ (node กลายเป็น None) ทำให้โปรแกรม error โครงลูป while node จัดการให้แล้วเพราะมันหยุดเองเมื่อ node เป็น None

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

# LeetCode ให้ class นี้มาให้แล้ว ที่เขียนไว้ตรงนี้เพื่อให้บล็อกนี้รันได้เองทั้งก้อน
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# class TreeNode:
#     def __init__(self, val=0, left=None, right=None): ...

def search_bst(root, val):
    node = root                  # เริ่มที่ราก
    while node:                  # ยังไม่หลุดขอบต้นไม้
        if val == node.val:
            return node          # เจอ node ที่ต้องการ คืนทั้ง subtree
        elif val < node.val:
            node = node.left     # ค่าที่หาเล็กกว่า ต้องอยู่ทางซ้าย
        else:
            node = node.right    # ค่าที่หาใหญ่กว่า ต้องอยู่ทางขวา
    return None                  # เดินจนตกขอบต้นไม้ แปลว่าไม่มี

# BST [4, 2, 7, 1, 3]
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
found = search_bst(root, 2)
print(found.val, found.left.val, found.right.val)   # ได้ subtree ที่มีราก 2
print(search_bst(root, 5))                          # ไม่มีค่า 5 ใน BST นี้

Output

2 1 3
None

ข้อนี้คือการนำกฎ BST มาใช้ตรง ๆ แทนที่จะ iterate ดูทุก node แบบ tree ทั่วไป (ซึ่งจะเป็น O(n)) เราใช้ความจริงที่ว่าค่าถูก sort ไว้แล้ว ทุกครั้งที่ compare เราตัดทิ้งครึ่งหนึ่งของ tree ที่เป็นไปไม่ได้ทันที เช่นถ้า val น้อยกว่า node ปัจจุบัน เราไม่มีทางเจอมันในฝั่งขวา (ฝั่งขวาใหญ่กว่าหมด) จึงไปซ้ายอย่างเดียว

จะเขียนแบบ recursion (การเรียกตัวเอง) ก็ได้ ผลเหมือนกัน แต่แบบ loop (วน) ประหยัด memory กว่าเพราะไม่ต้องใช้ call stack ถ้าเปลี่ยนเป็น recursion โค้ดจะสั้นลงแต่กิน memory เพิ่มตาม height (ความสูง)

Time O(h) traverse ลงจาก root ถึง leaf (ใบ) มากสุดเท่า height h · Space O(1) แบบ loop ใช้ตัวแปรเดียว (ถ้าเขียน recursion จะเป็น O(h) จาก call stack)

💡 สรุป pattern

เมื่อโจทย์ให้ BST มา ให้คิดถึงการ traverse ลง tree โดย compare ค่าแล้วเลือกทิศ วิธีนี้ตัดปัญหาลงครึ่งทุกก้าว เอาไปใช้กับ search insert และ delete ใน BST ได้ทั้งหมด