LISP Binary Trees - Maximum Depth
Using this way of representing trees: (A (B) (C (D) (E))) (which from what I've seen, I think this is the standard way, but I could be wrong).
A
/ \
B C
/ \
D E
I want to find the maximum depth and build a list with nodes from the root to that level. In the example above, the answer would be 2 (the root is at level 0) with one of the following two lists: (ACD) or (ACE).
The maxdepth algorithm should be simple:
maxdepth( tree ):
if ( !tree ) return 0
leftdepth = maxdepth( left sub-tree )
rightdepth = maxdepth( right sub-tree )
return max ( leftdepth + 1, rightdepth + 1 )
So, I tried something like this:
(defun maxdepth(l)
(cond
((null l) 0)
((atom l) 0)
((+ 1 (max (maxdepth(car l)) (maxdepth(cdr l)))))
)
)
The CAR tree should give me the left subtree, and the CDR tree should give me the correct one. If I get to the end or the atom (that's wrong), I stop. I check if maxdepth (car l) is greater than maxdepth (cdr l) and move on with more. But this gives me 8 for the above tree. And I haven't started building the list yet.
How far from a good idea and good implementation am I?
I figured out that your requirement is that you want to return two values: depth and one (arbitrary) path from root to full depth. This is a good opportunity to show how you can use multiple value semantics.
At the root, the skeleton looks like this (assuming a binary tree):
(defun max-depth (tree)
(if (null (rest tree))
(values 0 tree)
(with-sub-depths (left-depth left-path right-depth right-path tree)
(if (> right-depth left-depth)
(values (1+ right-depth) (cons (car tree) right-path))
(values (1+ left-depth) (cons (car tree) left-path))))))
With-sub-depths
now is the placeholder for the actual recursion.
Assuming we get this max-depth
will return the desired two values. If we just call it and use its return value, we get the first (primary) value:
(let ((d (max-depth tree)))
(format t "Depth is ~a." d))
If we need additional values, we can use multiple-value-bind
:
(multiple-value-bind (depth path) (max-depth tree)
(format t "Depth is ~a. Example path: ~s." depth path))
Now we need to use multiple-value-bind
in recursion:
(defun max-depth (tree)
(if (null (rest tree))
(values 0 tree)
(multiple-value-bind (left-depth left-path) (max-depth (second tree))
(multiple-value-bind (right-depth right-path) (max-depth (third tree))
(if (> right-depth left-depth)
(values (1+ right-depth) (cons (first tree) right-path))
(values (1+ left-depth) (cons (first tree) left-path)))))))
Trying it at the REPL displays all return values:
CL-USER> (max-depth '(A (B) (C (D) (E))))
2
(A C D)
In the view you are using, the (car l)
current node (cadr l)
is the left subtree and (caddr l)
is the right subtree. So your recursive step should be:
(+ 1 (max (maxdepth (cadr l)) (maxdepth (caddr l)))
You are also missing the clause t
in your default sentence cond
. So the full version should be:
(defun maxdepth (l)
(cond ((null l) 0)
((atom l) 0)
(t (+ 1 (max (maxdepth (cadr l)) (maxdepth (caddr l)))))))
(maxdepth '(A (B) (C (D) (E))))
returns 3