Ý tưởng 1

Gọi ~cnt_i~ là đếm số node và lá có độ cao là i

Dễ thấy với từng ~i~ độ cao muốn nó thành một cây nhị phân đầy đủ thì số lượng node và lá có độ cao là ~i~ đều phải là một số chẵn, để đếm số lượng node và lá có độ cao là ~i~ thì ta có các nhận xét như sau:

• Tổng số lượng node có độ cao ~i~ bằng tổng số node và lá có độ cao là ~i+1~ chia cho ~2~ hay ~\frac{cnt_{i+1}}{2}~

Vậy ta chỉ cần duyệt ngược lại từ độ cao cao nhất về độ cao là ~1~, mỗi lần duyệt ta kiểm tra xem với độ cao ~i~ có số lượng node và lá là ~cnt_i~ thì nó có thỏa mãn là cây nhị phân không khi và chỉ khi ~cnt_i~ là một số chẵn và nếu thỏa mãn thì ta cập nhật số lượng node và lá cho độ cao ~i-1~

Lưu ý: Ta cần phải xét xem số lượng gốc của cây hay là ~cnt_0~ có thỏa mãn luôn luôn bằng ~1~, nếu thỏa mãn cùng với điều kiện trên thì đây là cây nhị phân đầy đủ.

Ý tưởng 2

Sử dụng hàng đợi ưu tiên - priority queue để mô phỏng lại cách từ lá lên đỉnh gốc

Gọi ~pq~ là tập hợp độ cao của nút lá và phần tử đầu tiên của ~pq~ chính là nút lá có độ sâu cao nhất

Khi ~pq~ vẫn còn nhiều hơn ~1~ phần tử thì ta sẽ lấy trong ~pq~ hai phần tử mỗi lượt là:

• ~best~ là nút lá có độ cao cao nhất

• ~secondBest~ là nút lá có độ cao cao nhì ( tức có độ cao bé hơn hoặc bằng ~best~ )

Nếu ~best = secondBest~ thì ta sẽ thêm vào ~pq~ độ cao ~best-1~ ( hoặc ~secondBest-1~ ) và có khả năng tạo được cây nhị phân đày đủ, ngược lại không thể tạo được cây nhị phân đầy đủ

Vậy chạy đến khi ~pq~ chỉ còn ~1~ phần tử thì kiểm tra xem phần tử còn lại duy nhất trong ~pq~ đó có độ cao bằng ~0~ hay không, nếu không thì không thể tạo được cây nhị phân đầy đủ, ngược lại thì tạo được.