In this paper, an airway labeling algorithm that allows for gaps between the labeled branches is introduced. A bottom-up approach for arriving to an optimal set of branches and their associated labels is used in the proposed method. A K nearest neighbor based appearance model is used to differentiate the different anatomical branches. The proposed method was applied on 33 computed tomography scans of different subjects, where an average of 24 anatomical branches were correctly detected out of a total of 29 anatomical branches. Additionally, the proposed method was also evaluated on trees with simulated errors, such as missing branches and having falsely detected branches, where we showed that such errors have little or no effect on the proposed method.