Vấn đề tìm mã tiền tố tối ưu (optimal prefix-free codes) cho chi phí chữ cái không bằng nhau bao gồm việc tính toán mã tiền tố chi phí tối thiểu mà bảng chữ mã hóa gồm các chữ cái chi phí (độ dài) không bằng nhau, độ dài α và β, với α ≤ β. Chúng ta giới hạn trong cây nhị phân.
Mã được biểu diễn bằng cây lệch (lopsided tree), tương tự như cây Huffman biểu diễn giải pháp bài toán mã hóa Huffman. Dù có sự tương đồng, trường hợp chi phí chữ cái không bằng nhau khó hơn nhiều bài toán Huffman cổ điển; không có thuật toán thời gian đa thức nào được biết cho chi phí chữ cái chung, dù có tài liệu phong phú về vấn đề này.
Tuy nhiên, có thuật toán thời gian đa thức đã biết khi α và β là hằng số nguyên.
Vấn đề tính cây chi phí nhỏ nhất trong trường hợp này được nghiên cứu đầu tiên bởi Karp năm 1961, người giải quyết bằng quy hoạch tuyến tính nguyên (integer linear programming), tạo ra thuật toán mũ theo cả n và β. Kể từ đó có nhiều công trình về các khía cạnh như: chặn chi phí cây tối ưu; giới hạn trường hợp đặc biệt khi tất cả trọng số bằng nhau.
Dù nỗ lực đó, vẫn chưa biết bài toán cơ bản có giải được trong thời gian đa thức hay là NP-complete.
Golin và Rote mô tả thuật toán quy hoạch động O(nβ+2) xây dựng cây theo kiểu top-down.
Điều này đã được cải tiến bằng cách tiếp cận khác (khái niệm ma trận đơn điệu, ví dụ: tính chất Monge và thuật toán SMAWK).
ĐỊNH LÝ 1: Cây lệch tối ưu có thể xây dựng trong O(nβ) thời gian.
Đây là thuật toán hiệu quả nhất biết cho trường hợp β nhỏ; thực tế chi phí chữ cái thường nhỏ (ví dụ: mã Morse).
Gần đây, một lược đồ thuật toán xấp xỉ hiệu quả đã được đưa ra.
ĐỊNH LÝ 2
Tồn tại lược đồ xấp xỉ thời gian đa thức (polynomial time approximation scheme) cho cây lệch tối ưu.