What is the time complexity of finding the height of a binary tree with n nodes?

Đáp án đúng: "O(n)". Muốn biết chiều cao thì phải so chiều cao của hai cây con tại mỗi nút, nghĩa là thăm mọi nút đúng một lần và làm một lượng việc hằng số ở mỗi nút, cho chi phí tỉ lệ với số nút. "O(log n)" sai vì đây là chiều cao của một cây nhị phân cân bằng, tức là giá trị kết quả có thể nhỏ, chứ không phải chi phí tìm ra nó; hơn nữa cây có thể suy biến thành một chuỗi dài. "O(n^2)" sai vì phép duyệt không có vòng lặp lồng nhau nào, mỗi nút không bị thăm lại nhiều lần. "O(n log n)" sai vì đây là chi phí đặc trưng của các thuật toán sắp xếp dựa trên so sánh, không phát sinh khi chỉ đi một lượt qua cây.