August 19, 2024
P56 - Symmetric binary trees
Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a function symmetric to check whether a given binary tree is symmetric. We are only interested in the structure, not in the contents of the nodes.
lisp
;;; symmetric tree
;;; predicate, returns t when the right subtree is the mirror image of
;;; the left subtree (ignoring content)
(defun symmetric (tree)
(or (null tree)
(equal-structure (second tree) (revert (third tree)))
)
)
(defun revert (tree)
(if (null tree)
()
(list (first tree) (revert (third tree)) (revert (second tree)))
)
)
(defun equal-structure (t1 t2)
(cond
((null t1) (null t2))
((null t2) nil)
(t (and (equal-structure (second t1) (second t2))
(equal-structure (third t1) (third t2))
)
)
)
)
Be first to comment