Balanced Binary Tree: tại sao bạn cần ngừng tính lại chiều cao

Height-balanced nghĩa là mọi node trong cây thỏa mãn một điều kiện: chiều cao của subtree trái và subtree phải chênh nhau không quá một. Không chỉ node gốc. Mọi node. Yêu cầu toàn cục đó là lý do khiến giải pháp naive chậm — kiểm tra balance ở root thì dễ, nhưng xác nhận ở khắp mọi nơi buộc bạn phải thăm mọi node, và mỗi lần thăm lại kích hoạt tính toán chiều cao riêng nếu bạn không cẩn thận.

Cây trên là balanced. Node 9 có chiều cao 1, node 20 có chiều cao 2 — chênh lệch ở root là 1, chấp nhận được. Mọi subtree cũng pass: hai con của node 20 đều có chiều cao 1. Bây giờ thêm con trái vào node 9 và thêm con trái vào node đó thì bạn có ví dụ unbalanced điển hình — độ sâu chồng chất về một phía trong khi phía kia vẫn phẳng.

Đề bài

Cho một binary tree, xác định liệu nó có phải là height-balanced hay không — tức là mọi node trong cây đều có subtree trái và phải với chiều cao chênh nhau không quá một. Full statement: LeetCode 110.

Ràng buộc:
- Số lượng node trong cây nằm trong khoảng [0, 5000].
- -104 <= Node.val <= 104

Constraints nói gì

Bài toán cho phép tối đa 5000 node và giá trị trong [-10^4, 10^4]. Dải giá trị không liên quan — balance hoàn toàn là tính chất cấu trúc. Số lượng node mới là thứ thú vị.

n <= 5000 không loại bỏ O(n²). Một giải pháp O(n²) chạy tối đa 25 triệu phép tính, đủ nhanh trên mọi máy hiện đại. Vậy nên constraints không bắt buộc bạn phải tìm giải pháp tối ưu. Thứ bắt buộc là hiểu tại sao approach naive lãng phí và liệu có thể làm tốt hơn — và có thể, với một pass duy nhất.

Cây có thể rỗng (n = 0), và cây rỗng là balanced theo định nghĩa. Trường hợp này rơi ra tự nhiên từ bất kỳ implementation đúng nào miễn là bạn xử lý null node.

Approach 1: top-down tính lại chiều cao

Cách đọc trực tiếp nhất từ định nghĩa bài toán: với mỗi node, tính chiều cao của subtree trái và phải, kiểm tra chênh lệch không quá 1, rồi recurse vào hai con.

class Solution:
    def isBalanced(self, root) -> bool:
        if not root:
            return True
 
        left_h = self.getHeight(root.left)
        right_h = self.getHeight(root.right)
 
        if abs(left_h - right_h) > 1:
            return False
 
        return self.isBalanced(root.left) and self.isBalanced(root.right)
 
    def getHeight(self, node) -> int:
        if not node:
            return 0
        return 1 + max(self.getHeight(node.left), self.getHeight(node.right))

public class Solution {
    public bool IsBalanced(TreeNode root) {
        if (root == null) return true;
 
        int leftH = GetHeight(root.left);
        int rightH = GetHeight(root.right);
 
        if (Math.Abs(leftH - rightH) > 1) return false;
 
        return IsBalanced(root.left) && IsBalanced(root.right);
    }
 
    private int GetHeight(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.Max(GetHeight(node.left), GetHeight(node.right));
    }
}

Đây hoạt động đúng. Logic rõ ràng và code ánh xạ trực tiếp từ định nghĩa. Vấn đề là công việc dư thừa. Khi IsBalanced được gọi ở root, GetHeight duyệt toàn bộ cây để tính chiều cao của các subtree gốc. Sau đó IsBalanced recurse vào con trái, và GetHeight duyệt lại subtree đó — bao gồm tất cả node trong các con của subtree đó. Mỗi node trong cây đóng góp vào nhiều tính toán chiều cao. Trong trường hợp xấu nhất, một cây cân bằng có chiều cao h khiến mỗi node ở độ sâu d có subtree của nó được duyệt h - d lần. Đó là O(n log n) cho cây balanced và O(n²) cho chuỗi lệch.

Time và space complexity

Time: O(n²) worst case. Với cây lệch hoàn toàn về trái gồm n node (một chuỗi), root kích hoạt tính chiều cao trên toàn bộ n node. Con trái của root kích hoạt trên n - 1 node. Cứ thế tiếp tục. Tổng: n + (n-1) + ... + 1 = n(n+1)/2.

Space: O(n) cho call stack. Độ sâu recursion bằng chiều cao cây, là O(n) với chuỗi lệch.

Approach 2: bottom-up — chiều cao và balance trong một pass

Insight là getHeight và isBalanced đang thực hiện công việc chồng lên nhau trên cùng các node. Bạn không cần tách chúng ra. Thay vào đó, viết một hàm duy nhất trả về chiều cao của một subtree nếu nó balanced, hoặc một sentinel value (-1) nếu không. Xử lý con trước, rồi mới đến cha — post-order traversal.

class Solution:
    def isBalanced(self, root) -> bool:
        def check(node) -> int:
            if not node:
                return 0
 
            left_h = check(node.left)
            if left_h == -1:
                return -1
 
            right_h = check(node.right)
            if right_h == -1:
                return -1
 
            if abs(left_h - right_h) > 1:
                return -1
 
            return 1 + max(left_h, right_h)
 
        return check(root) != -1

public class Solution {
    public bool IsBalanced(TreeNode root) {
        return Check(root) != -1;
    }
 
    private int Check(TreeNode node) {
        if (node == null) return 0;
 
        int leftH = Check(node.left);
        if (leftH == -1) return -1;
 
        int rightH = Check(node.right);
        if (rightH == -1) return -1;
 
        if (Math.Abs(leftH - rightH) > 1) return -1;
 
        return 1 + Math.Max(leftH, rightH);
    }
}

Sentinel -1 là quyết định thiết kế then chốt. Chiều cao thực luôn không âm, nên -1 rõ ràng là "subtree này unbalanced, dừng lan truyền." Một khi check(node.left) trả về -1, bạn short-circuit ngay lập tức — thậm chí không gọi check(node.right). Tín hiệu imbalance lan lên call stack và toàn bộ hàm trả về trước khi duyệt các nhánh không cần thiết.

Trace tay qua Example 1: [3, 9, 20, null, null, 15, 7]

Thứ tự xử lý là post-order — lá trước:

• Bước 1: check(9). Cả hai con đều null, trả về 0 mỗi cái. |0 - 0| = 0 <= 1. Trả về 1 + max(0, 0) = 1.
• Bước 2: check(15). Cả hai con đều null. Trả về 1.
• Bước 3: check(7). Cả hai con đều null. Trả về 1.
• Bước 4: check(20). Trái trả về 1, phải trả về 1. |1 - 1| = 0 <= 1. Trả về 1 + max(1, 1) = 2.
• Bước 5: check(3). Trái trả về 1, phải trả về 2. |1 - 2| = 1 <= 1. Trả về 1 + max(1, 2) = 3.

Kết quả cuối: check(root) = 3, không phải -1, nên isBalanced trả về true.

Bây giờ trace trường hợp unbalanced [1, 2, 2, 3, 3, null, null, 4, 4]:

• check(4) và check(4) (các lá): cả hai trả về 1.
• check(3) (con trái của node-2-trái): trái = 1, phải = 1. Trả về 2.
• check(3) (con phải của node-2-trái): cả hai con đều null. Trả về 1.
• check(2) (con trái của root): trái = 2, phải = 1. |2 - 1| = 1 <= 1. Trả về 3.
• check(2) (con phải của root): cả hai con đều null. Trả về 1.
• check(1) (root): trái = 3, phải = 1. |3 - 1| = 2 > 1. Trả về -1.

check(root) == -1, nên isBalanced trả về false.

Time và space complexity

Time: O(n). Mỗi node được thăm đúng một lần. Không có traversal dư thừa.

Space: O(h) trong đó h là chiều cao cây. Best case O(log n) với cây cân bằng, worst case O(n) với chuỗi lệch. Độ sâu call stack bằng chiều cao cây.

Các edge case

Cây rỗng (root = null). Cả hai approach trả về true ngay lập tức — hoặc từ null check trong isBalanced, hoặc từ check trả về 0 (không phải -1). Cây rỗng thỏa mãn định nghĩa balance theo nghĩa vacuous.

Một node duy nhất. Con trái và phải của node đó đều null, nên chênh lệch chiều cao là 0. Trả về true. Không có gì phức tạp ở đây.

Chuỗi lệch hoàn toàn về phải ([1, null, 2, null, 3, ...]). Với approach top-down đây là worst case: O(n²) vì getHeight duyệt toàn bộ chuỗi còn lại ở mỗi level. Với bottom-up, mỗi node vẫn chỉ được thăm một lần — O(n) bất kể hình dạng. Chuỗi lệch cũng là worst case về space trong cả hai: O(n) độ sâu stack.

Subtree gần như balanced. Định nghĩa yêu cầu mọi node đều thỏa mãn điều kiện, không chỉ root. Một cây như [1, 2, 3, 4, 5, null, null, 6] có thể trông balanced ở root nhưng có subtree unbalanced sâu bên dưới. Approach bottom-up bắt được điều này tự nhiên — imbalance lan lên trên như -1 mà không cần logic bổ sung. Approach top-down cũng bắt được nhưng tính lại chiều cao không cần thiết.

Node.val ở biên (-10^4 và 10^4). Giá trị không ảnh hưởng đến balance. Thuật toán không bao giờ đọc node.val — bạn có thể bỏ qua biên này hoàn toàn.

So sánh

Space của bottom-up là O(h) chứ không phải O(n) — với cây cân bằng đó là O(log n), một cải thiện thực sự dù worst case vẫn là O(n) với chuỗi lệch.

Approach nào tôi sẽ ship

Bottom-up, ngay lập tức, cho bất kỳ sử dụng production nào. Phiên bản top-down có sức hấp dẫn là gần như là bản transcription trực tiếp của đề bài — và trong interview, viết nó trước để xác nhận bạn hiểu định nghĩa là chiến lược hợp lý. Nhưng dừng ở đó, giải thích sự dư thừa, rồi viết phiên bản bottom-up.

Pattern mà approach bottom-up thể hiện đáng được đặt tên: dùng sentinel return value để mang tín hiệu thất bại lên recursion mà không cần biến global hay pass riêng biệt. Bạn thấy điều này trong Diameter of Binary Tree (543), nơi bạn mang diameter như một side-channel trong khi trả về chiều cao từ hàm đệ quy. Ý tưởng là post-order traversal cho bạn một điểm tích lũy tự nhiên — khi bạn xử lý một node, bạn đã có đầy đủ thông tin từ cả hai subtree.

Sentinel -1 là một lựa chọn. Một lựa chọn khác là trả về tuple (is_balanced, height). Sentinel gọn hơn; tuple rõ ràng hơn. Cả hai đều đúng; chọn cái mà team của bạn có thể đọc mà không cần comment.

Vị trí trong series trees

Đây là bài thứ tám trong series, sau Validate BST (98) và Subtree of Another Tree (572). Ba primitive duyệt cây — DFS recursion, BFS với queue, tích lũy post-order — đã được thiết lập trước đó. Balanced Binary Tree là bài đầu tiên trong series làm cho sự kém hiệu quả của naive top-down traversal trở nên cụ thể. Pattern bottom-up được giới thiệu ở đây xuất hiện liên tục về sau.

Diameter of Binary Tree (543) là bài tiếp nối trực tiếp nhất. Bạn dùng cùng post-order pass nhưng thay vì mang failure sentinel, bạn mang cả chiều cao lẫn diameter khi return từ mỗi lời gọi đệ quy. Kỹ thuật cấu trúc là giống hệt.

Maximum Depth of Binary Tree (104) đơn giản hơn nhưng dùng cùng tính chiều cao bottom-up. Nếu 104 có vẻ trivial, 110 cho thấy chính xác tại sao tính chiều cao quan trọng hơn trường hợp rõ ràng.

Path Sum II (113) đi theo hướng khác: thay vì tích lũy kết quả từ con khi quay lên, bạn truyền state xuống và ghi lại các path hoàn chỉnh ở lá. Sự tương phản làm rõ khi nào nên đẩy thông tin xuống và khi nào nên kéo lên.

Binary Tree Maximum Path Sum (124) là phiên bản hard của pattern này. Bạn mang cả giá trị "single path" (return hữu ích) lẫn giá trị "complete path qua node này" (cập nhật side-channel cho global max). Kỹ thuật sentinel từ 110 và kỹ thuật side-channel từ 543 đều xuất hiện ở đó, dưới constraints khó hơn.