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?
source to share
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)
source to share
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
source to share