前言

昨天有舉一個 tree 的例子，每組父子關係都正確、整棵 Tree 卻不是 BST，因為 15 落在 9 的左 subtree 裡，卻比 9 大。原因是 BST 的規則管的是整棵 subtree，不是只有直接接在下面那兩顆 node。

那要怎麼驗證目前的 tree 具有 BST 規則呢？今天就來看看～

另外，這也是 LeetCode 上的題目 98. Validate Binary Search Tree，當時自己寫卡了很久，所以想記錄下來我從一開始的嘗試，到後來摸索出解法的流程～

初版：一段看起來對的驗證程式

一段只比較父子的遞迴

BST 規則是左邊比較小、右邊比較大，我第一時間想到的解法，就是走過每一顆 node，各自和它的左右 child 比一次：

function isValidBST(node) {
  if (node === null) return true;

  if (node.left !== null && node.left.value >= node.value) return false;
  if (node.right !== null && node.right.value <= node.value) return false;

  return isValidBST(node.left) && isValidBST(node.right);
}

這段程式的邏輯乍看沒什麼問題，它走到了每一顆 node，也把規則寫成了比較式，左 child 不能大於等於自己、右 child 不能小於等於自己，兩邊都過了才繼續往下遞迴，任何一顆 node 出問題都會讓 && 短路、一路回傳 false。拿昨天那些合法的 BST 餵給它，它也都會正確的回傳 true。

這裡用的是 >= 和 <= 而不是 > 和 <，昨天採用的政策是不允許重複，也就是規則寫成沒有例外的「左 < node < 右」，所以值相等的時候就該判定失敗。今天三段程式都沿用這個政策，後面不再重複說明。

一個反例就推翻 🤯

現在換一棵 Tree 來看：

圖 1 本篇要檢查的 Tree：root 是 10，12 掛在 5 的右邊

把四組父子關係逐一檢查一遍：5 < 10 通過、15 > 10 通過、3 < 5 通過、12 > 5 通過。四組全部合格，初版那段程式會回傳 true。

問題是這棵 Tree 不是 BST。12 在 10 的左 subtree 裡，而規則要求那整棵 subtree 的每一個值都小於 10，12 顯然不符合。

而我前面寫的初版驗證程式錯過了這件事，原因在於 12 和它的直接 parent 5 之間毫無矛盾，12 本來就該比 5 大。真正有衝突的是 12 和 10，而 10 是它的 grandparent，也就是 parent 的 parent，程式卻沒有把這兩顆放在一起比較。

既然如此，那把檢查的範圍往上多拉一層，連 grandparent 也一起比，是不是就補起來了呢？以這棵 Tree 來說，確實會被檢查到，可是把 Tree 再加深一點就又不夠了。想像 12 底下還掛著一顆更深的 node，它和 parent、grandparent 都沒有問題，卻違反了曾祖父那一層的限制。每補一層，就會有一種需要再多補一層才抓得到的情況，而 Tree 可以有多深沒有上限，這條路補不完。

錯的不是某一行，是它維持的性質不夠強

初版那段程式問題到底在哪呢？

初版程式每一行都在做正確的比較，只是它檢查的性質是「每顆 node 和它的直接 child 之間關係正確」，而 BST 要求的性質是「每顆 node 和它所有 ancestor 之間關係都正確」。前者只是後者的一部分，通過前者推不出後者。

因此要修的不是某個比較符號，而是得換一個更強的性質來檢查。

這條規則其實是一個 invariant

Day 04 談迴圈時出現過 Loop Invariant（迴圈不變量），指的是一句在迴圈每一輪開始前都成立的話，而 BST 規則是相同概念，只是成立的對象從「迴圈的每一輪」換成「Tree 的每一顆 node」。

這角度提供的另個觀點：既然要檢查的是「這句話有沒有在每一顆 node 上都成立」，那走到某一顆 node 的時候，就得先問清楚這顆 node 目前受到哪些限制，然後才有辦法判斷它有沒有違反。

檢查一顆 node，要知道它所有 ancestor 的限制

回到剛才那棵 Tree，看看 12 到底受了哪些限制。從 root 走到它的路線是先往左、再往右，而每轉一次彎就會多出一條限制：

圖 2 從 root 走到 12 一共轉了兩次彎，每一次都替 12 加上一條限制

往左那一步表示 12 進了 10 的左 subtree，所以它必須小於 10；往右那一步表示它進了 5 的右 subtree，所以它必須大於 5。兩條合起來，12 的合法範圍就是比 5 大、比 10 小。12 大於 5 沒問題，但它不小於 10，落在範圍外面。

這件事可以推廣到任何一顆 node，從 root 走到它的路線上有幾個轉彎，它就受到幾條限制，每一條的方向由「當初往左走還是往右走」決定。一顆位於第五層的 node，頭上有四個 ancestor，要正確檢查它，這四條限制就要全部到齊。

保存所有 ancestor 可以嗎

順著這個想法，直覺的做法可能是走訪時帶著一份 ancestor 清單，每往下一層就把目前這顆 node 連同走的方向記進去，檢查某顆 node 時就拿清單裡的每一筆逐一比對。這做法沒錯，它確實抓得到 12，也不會漏掉任何深度的違規，因為它把定義裡要求的每一條限制都真的檢查了一次。

圖 3 每往下一層，清單就多一筆；Tree 歪成一條線時，最深的那顆得和它上面每一顆都比過

問題在成本，每顆 node 都要和它全部的 ancestor 比一次，比較的次數就等於所有 node 的 depth。Tree 夠平衡的時候還好，多數 node 的 depth 都在 log N 附近，總數大約是 N log N；但 BST 也可能歪成一條線，那時第 k 顆 node 頭上就有 k - 1 個 ancestor，總比較次數變成 1 + 2 + ⋯ + (N-1)，也就是大約 N²/2。

另外，清單的長度本身也是個麻煩，ancestor 有幾個取決於這顆 node 在第幾層，而深度又取決於 Tree 長成什麼形狀，因此事先不可能知道要準備多大的空間，只能一路往下一路長。

到這裡，要解決的問題似乎又變了，一開始問的是「怎麼檢查一棵 Tree」，現在卡住的卻是「走訪的時候，身上要帶著什麼資訊，才夠判斷眼前這顆 node 合不合格」。這個被帶著走、每到一顆 node 就更新一次的資訊，一般稱為走訪的狀態 (state)。初版那段只比較父子的程式就是完全沒有 state；ancestor 清單則是 state 太大，大到會隨著深度一直長。

那有沒有辦法，把數量可能很大、也可能很小的 state，壓縮成大小固定的 state 呢？

解法一：把 ancestor 的限制壓縮成一個範圍

每顆 node 都有一個合法區間

壓縮的線索，在剛才替 12 列限制的時候就出現過了，所有 ancestor 給的限制，形式都是「必須小於某個值」或「必須大於某個值」，如果將這種限制疊在一起，效果等於一個下界加一個上界。12 受到「大於 5」和「小於 10」兩條限制，合起來就是區間 (5, 10)。就算頭上有四個、四十個 ancestor，最後也只會收斂成兩個數字，因為多個下界裡只有最大的那個有效，多個上界裡也只有最小的那個有效。

走訪的時候，每顆 node 要帶的不是一串 ancestor，而是一組 (min, max)，node 的值必須落在這個開區間裡面。而 root 頭上沒有任何 ancestor、什麼限制都沒有，它的區間是 (-∞, +∞)。

往左走縮上界，往右走縮下界

區間怎麼從上一層傳到下一層呢？想像站在某顆 node 上，準備往它的左 child 走。BST 規則說這顆 node 的整棵左 subtree 都必須小於它，所以左 child 以及它底下的每一顆，上界都換成這顆 node 的值。至於下界，左 subtree 沒有帶來新的限制，原本從上層繼承來的那個繼續沿用。

往右 child 走則狀況相反，右 subtree 的所有值都必須大於這顆 node，於是下界換成這顆 node 的值，上界沿用。規則整理起來就這兩條：

拿它跑一次剛才那棵 Tree，從 root 出發：

12 在這裡被抓到了，而要注意的是，抓到它的並不是 12 和某一顆 node 比較的結果，而是它收到的那個區間，而那個區間是 10 和 5 兩顆一路傳下來的，10 貢獻上界、5 貢獻下界。

把 12 搬到合法的位置，也可以看出同一件事，它其實該掛在 15 的左邊，這時從 root 走到它的路線變成「先往右、再往左」，收到的區間就是 (10, 15)，12 落在裡面，通過。同一個值、同一棵 Tree，而且兩種擺法的父子關係各自都是對的——違規那次 12 掛在 5 的右邊，12 > 5 沒問題；合法這次掛在 15 的左邊，12 < 15 也沒問題。只因為站的位置換了，判定就從失敗變成通過。

圖 4 區間從 root 的 (-∞, +∞) 每往下一層就換掉一邊的界線；同一顆 12 換一個位置，收到的區間就從 (5, 10) 變成 (10, 15)

寫成遞迴

把往左往右那兩條規則寫成程式，就是一段帶著區間往下走的遞迴：

function isValidBST(root) {
  function valid(node, min, max) {
    if (node === null) return true;

    if (node.value <= min || node.value >= max) return false;

    return valid(node.left, min, node.value)
        && valid(node.right, node.value, max);
  }

  return valid(root, -Infinity, Infinity);
}

和初版那段程式比起來，差別只在多了兩個參數。少了它們，每一層就只認得眼前這三顆 node；有了它們，每一層都知道自己被上面所有 ancestor 框在什麼範圍內。這種一路往下鑽到底的走法 Day 19 提過，叫做深度優先走訪 (DFS)，區間就跟著這條路一起往下傳。

-Infinity 和 Infinity 是 JavaScript 裡現成的值，剛好可以拿來表示「這個方向還沒有限制」。有些語言沒有這種值，做法通常是改傳 null 進去，判斷的時候多加一個「如果邊界是 null 就不檢查這一側」的條件，效果是一樣的。

為什麼傳範圍就等於檢查了整條規則

這段程式現在確實抓得到反例了，不過抓得到這一個反例，和「所有違規的 Tree 都抓得到」是兩件事。要確認後者也成立，可以照 Day 04 那套方式，把「每顆 node 拿到的區間，正確反映了它所有 ancestor 的限制」當成要維持的那句話，看它在每一層成不成立。

Initialization：root 拿到的是 (-∞, +∞)，而 root 頭上沒有任何 ancestor、確實不受任何限制，所以這句話在第一層成立。

Maintenance：假設某顆 node 拿到的區間是對的，看看它的左 child。左 child 的 ancestor，就是這顆 node 的 ancestor 再加上這顆 node 自己；前者的效果原封不動繼承下來，後者要求「必須小於這顆 node 的值」，而這正好就是把上界換成這顆 node 的值。右 child 的推導對稱。因此只要某一層成立，它的下一層也會成立。

Termination：遞迴在碰到 null 時結束，代表整棵 Tree 每一顆 node 都被走過、也都拿到了正確的區間並通過檢查。而「每顆 node 都落在自己所有 ancestor 允許的範圍內」，就是 BST invariant 的完整內容，所以程式回傳 true 的時候，這棵 Tree 確實是一棵合法的 BST。

解法二：inorder 必須嚴格遞增

走訪順序本身就是一次檢查

除了往下傳限制，還有另一條路可以走，Day 19 介紹過 inorder 的順序是先走完左 subtree、再處理自己、最後走右 subtree，而昨天也看過，在一棵合法的 BST 上用 inorder 走一遍，走出來的序列剛好由小到大。

既然合法的 BST 一定產生嚴格遞增的序列，那反過來，只要走出來的序列有任何一個地方沒有遞增，這棵 Tree 就不是 BST。用剛才那棵有問題的 Tree 試試，inorder 的結果是 3 → 5 → 12 → 10 → 15，12 後面跟著 10，這一處就沒有遞增。

不必存整串序列，只要記上一個值

聽到「檢查序列有沒有遞增」，直覺可能是先把走訪結果全部收進一個陣列，再從頭掃一遍看看每一格是不是都比前一格大。這樣做沒問題，而且程式很好懂，走訪和檢查是兩個各自獨立的步驟，代價是它把整棵 Tree 的值複製了一份，額外空間變成 O(N)。

判斷某一個值合不合格，需要的資訊只有一個，就是上一個被走訪到的值，只要每一顆 node 都比它的前一顆大，整串自然就是遞增的，更早的那些值留著也用不到，因此要保存的 state 就只有一個變數：

function isValidBST(root) {
  let previous = null;

  function traverse(node) {
    if (node === null) return true;

    if (!traverse(node.left)) return false;

    if (previous !== null && previous >= node.value) return false;
    previous = node.value;

    return traverse(node.right);
  }

  return traverse(root);
}

previous 一開始是 null，代表還沒有走訪過任何 node，序列的第一個值不必和誰比較。之後每處理完一顆 node 就更新它，讓下一顆拿去比，拿它跑一次那棵有問題的 Tree，過程是這樣：

圖 5 inorder 依序處理 3、5、12、10，走到 10 的時候 previous 是 12，比它大

這裡有個地方容易寫錯，就是 previous 必須是整段程式共用的同一個變數，宣告在 traverse 外面。如果把它改成參數、跟著遞迴一起傳進去，程式看起來幾乎一樣，卻會失效，因為參數是每一層各自的區域變數，某一層更新了它，回到上一層之後那個更新就不見了，而 inorder 的下一顆常常正是在回到上層之後才處理到。這種寫法拿剛才那棵違規的 Tree 去跑，會回傳 true。

為什麼序列遞增就代表整棵 Tree 合法

前面說的是「合法的 BST 一定產生遞增序列」，可是這段程式用的是反過來的那一句：「序列遞增，所以這棵 Tree 合法」。這兩句話並不會自動互相成立，反過來的那句也得確認看看。

關鍵在 inorder 的順序有一個性質：對任何一顆 node 來說，它左 subtree 裡的值會連成一段、緊接著排在它前面，右 subtree 裡的值也會連成一段、緊接著排在它後面。這件事直接來自走訪的定義，中間不會插進其他 subtree 的值。以那棵合法的 Tree 為例，10 的位置左右兩側剛好就是它的左右 subtree 各自的成員。

如果整串序列嚴格遞增，那麼對任何一顆 node，排在它前面的每一個值都比它小，而它左 subtree 的成員全都在那一段裡面，所以左 subtree 的每一個值都小於它；右邊對稱，右 subtree 的每一個值都大於它。這兩句合起來，正好就是 BST invariant 在這顆 node 上的完整內容。而這個推論對序列裡的每一顆 node 都適用，整棵 Tree 因此合法。

兩種做法差在哪

時間都是 O(N)，額外空間都是 O(h)

先看時間，兩種做法都必須碰到每一顆 node，理由也一樣，因為只要有任何一顆沒被檢查，那顆就可能正是違規的那顆。每顆 node 各處理一次、每次做的事都是常數次比較，因此時間複雜度都是 O(N)。

額外空間的部分，兩段程式都是遞迴，主要成本來自 call stack，而 Day 19 算走訪成本時已經推過，同時疊在 call stack 上的就是從 root 到目前這顆 node 的那條路，最深就是 Tree 的 height，所以是 O(h)。range 那段在每一層多帶了兩個數字，但那是每層固定兩個、跟著 call stack 一起算；inorder 那段只有一個 previous，而且整段程式共用一個，兩者都不影響級別。也就是說，只看複雜度的話，兩種做法差不多：

重複值政策在兩段程式裡也各自落在一個地方。range 那段是 node.value <= min || node.value >= max 這兩個等號，inorder 那段則是 previous >= node.value 那一個。如果哪天改成允許相等的值往右掛，要鬆綁的就是這幾個符號，而不是去動走訪的邏輯。

state 的差別：合法邊界 vs 上一個值

真正的差別在那一欄 state，而且它們流動的方向也不一樣。range 的區間是沿著 link 由上往下傳的，parent 算好了交給 child，同一層的兩顆彼此互不相干；previous 則是沿著 inorder 的順序橫向傳遞，前一顆交給後一顆，兩顆在 Tree 上的位置關係完全不重要。像 3 和 5 是父子，12 和 10 卻是 grandchild 和 grandparent，在序列裡卻都只是相鄰而已。

圖 6 區間沿著 link 往下傳，previous 沿著走訪順序往後傳

這個差別還有一個看得見的後果：同樣判定這棵 Tree 不合法，兩段程式其實是在不同的 node 上發現問題的。range 那段在 12 就判定失敗，因為 12 自己落在區間 (5, 10) 外面；inorder 那段則是走到 10 才判定失敗，因為 10 比它前一顆 12 小。12 在 inorder 那段眼裡完全正常，它比前一顆 5 大，符合遞增；要等到下一顆進來，才看得出序列在這裡壞掉了。range 檢查的是「這顆 node 站對位置了嗎」，inorder 檢查的是「這顆 node 和前一顆的關係對嗎」，同一個違規，兩種角度會在不同的時間點看見它。

這個差別也影響了兩者好不好改寫。range 的區間既然只依賴 parent、不依賴走訪順序，那換一種走法也不影響結果，例如 Day 19 那個橫著走、一層看完再看下一層的層序走訪也可以，只要把待檢查的 node 連同它的區間一起放進 Queue 就行，額外空間就從「跟 Tree 的 height 有關」變成「跟最寬那一層有關」。inorder 那段就沒有這種彈性，它的正確性直接建立在走訪順序上，順序一換，遞增這個判準就不成立了。

反過來說，inorder 也有它順手的地方。它本來就在把整棵 Tree 由小到大走一遍，驗證的同時如果順便把值收起來，就能一併拿到排序好的結果；range 那段走訪的順序是由上往下，中途拿到的值沒有這種性質。

那實際上該挑哪一段呢？真的要分的話，range 那段的意圖比較直接，它逐字翻譯了 BST 規則本身，讀程式的人看到 (min, max) 大致就知道在做什麼；inorder 那段比較短，但它為什麼對，得先繞過「走訪順序」這一層才能理解。

通過驗證，不等於好用

今天兩段程式回答的是「這棵 Tree 合不合法」，而合法和好用與否無關。昨天那棵照排序插入、歪成一條線的 Tree 完全符合 BST 規則，今天兩種驗證都會回傳 true，但它的搜尋、插入、刪除全都是 O(N)。

時間複雜度取決於形狀，但形狀得另外衡量，要量的東西就是 Day 19 提到的 height，把 height 算出來和 log N 相比，就知道這棵 Tree 離「夠矮」還有多遠。

昨天也提到，實務上用的通常不是這種 BST，而是會在插入和刪除時自己動手調整形狀、把 Tree 維持在矮的狀態的版本。這類結構統稱平衡樹 (balanced tree)，常見的有 AVL Tree 和 Red-Black Tree，它們調整完之後仍然是合法的 BST，所以今天這兩種驗證照樣通過，變的只有形狀。

不過它們維持形狀的完整規則相當複雜，而多數語言和函式庫已經內建好了，需要一個既能維持順序又不會退化的結構時，通常是直接拿現成的來用，而不是自己實作一棵。這系列就不細部展開這些規則與實作～

小結

小小總結一下今天對驗證 BST 的認識～

• 為什麼只比較父子不夠？ 因為 BST 的規則限制的是整棵 subtree，一顆 node 必須同時滿足它所有 ancestor 給的限制。只檢查父子關係的程式，維持的性質比規則本身弱，通過了也推不出整棵 Tree 合法。
• range 與 inorder 差在哪？ 一個沿著 link 往下傳合法邊界，讓每顆 node 知道自己被框在什麼範圍內；一個沿著走訪順序往後傳上一個值，靠序列必須嚴格遞增來檢查。兩者的時間都是 O(N)、額外空間都是 O(h)，差別在 state 的形狀。
• 今天的核心是什麼？ 選對要保存的 state，才表達得出一個全域的規則。數量不固定的 ancestor 限制可以壓縮成兩個數字，整串走訪序列也可以壓縮成一個變數。

實際使用時，還可以記住幾件事～

• 值相等要判定失敗還是通過，取決於這棵 Tree 採用哪種重複值政策，寫檢查程式之前要先確認
• 驗證通過只代表結構合法，不代表操作會快，Tree 的形狀是另一回事

圖表說明：本文圖表由作者整理，並使用 Claude Code 協助繪製；內容與數據由作者確認。

Reference

• Master the Coding Interview: Data Structures + Algorithms
• 《A Common-Sense Guide to Data Structures and Algorithms, Second Edition》
• LeetCode 98：Validate Binary Search Tree
• Cornell CS 2112：Loop Invariants
• MIT 6.006：Binary Trees, Part 1
• Wikipedia：Binary search tree