;;; This is a hard problem.  One way to think about it: you need an
;;; auxiliary functions for constructing cbt with arbitrary start
;;; label at root.  Then you need to know the number of nodes in left
;;; and right subtrees.
;;; A table for that comes handy:
;;; N  / left size / p
;;;  1 / 0 / 
;;;  2 / 1 / 1
;;;  3 / 1 / 1
;;;  4 / 2 / 2
;;;  5 / 3 / 2
;;;  6 / 3 / 2
;;;  7 / 3 / 2
;;;  8 / 4 / 4
;;;  9 / 5 / 4
;;; 10 / 6 / 4
;;; 11 / 7 / 4
;;; 12 / 7 / 4
;;; 13 / 7 / 4
;;; 14 / 7 / 4
;;; 15 / 7 / 4
;;; 16 / 8 / 8
;;;
;;; Ok, except for the base N = 1, one can see that the left size
;;; depends essentially on the 2 higher-order bits (HOB) of N: if
;;; these two higer-order bits are "10", then left size keeps growing
;;; form a power of 2 by 1 unit; if the HOB are "11", then left size
;;; is constant, equal t the last value from the "10" series.
;;; 
;;; These two HOB are just N div p, where p is the value in the third
;;; colimn; and what needs to be added to form the left size in the
;;; "10" case is p + lower order bits, which is p + N mod p.  In the
;;; "11" case, this just gets to be p + (p-1).
;;;
;;; The starting label for subtrees is just 2k and 2k+1, if k is the
;;; starting label for the tree.

(defun complete-binary-tree (n)
  (cbt-label n 1)
  )

;;; cbt-label: complete binary tree with given label k at root;
;;; notice we also need an extra base case for n = 0.

(defun cbt-label (n k)
  (cond
   ((= n 0) nil)
   ((= n 1) (list k nil nil))
   (t (let* ((p (floor (highest-2-power n) 2))
	     (left (if (= 2 (floor n p))
		       (+ p (mod n p))
		     (+ p (1- p)))))
	(list k
	      (cbt-label left (* 2 k))
	      (cbt-label (- n 1 left) (+ 1 (* 2 k)))
	      )))
   )
  )

;;; highest-2-poer: that is less that or equal to n

(defun highest-2-power (n)
  (if (<= n 1)
      1
    (* 2 (highest-2-power (floor n 2)))
    )
  )