2

As I have been learning LISP and reading practical common lisp I have found problems and tried to solve them I have got stuck on this particular problem and am unsure of how to approach it so would like some help/advice.

I need to be able to create a postorder tree from its preorder and inorder

E.g if the following is given:

Preorder: A B D E C F

Inorder: D B E A C F

The output would be the postorder: D E B F C A

From what I can see the first element of the inorder is always the first element of the postorder so I have started writing code to reflect this:

(defun tree-recovery (preorder inorder)
  (let (root)
    (setf root (first inorder))))

But I am unsure of where to go from here, any help would be much appreciated! Thanks

Seth Carnegie
  • 73,875
  • 22
  • 181
  • 249
user1850231
  • 21
  • 1
  • 4

1 Answers1

2

If we name our function tree-recovery, let it recover the tree instead of building the postorder sequence. (Someone smarter than me is required to solve the problem without actual reconstruction of the tree).

Inorder and postorder start with the same element, but that element is not root: the first element of preorder sequence is the root.

Let's recover the tree, assuming that all sequence elements are non-nil atoms comparable by EQL. We will represent a leaf as a value of atom, other nodes as (list root left right), and an empty subtree as NIL.

(defun tree-recovery (preorder inorder)
  (if (rest preorder)
      (let* ((root (pop preorder))
             (inorder-root-tail
               (member root inorder))
             (inorder-left
               (ldiff inorder inorder-root-tail))
             (left-length
               (length inorder-left))
             (inorder-right
               (rest inorder-root-tail))
             (preorder-left
               (subseq preorder 0 left-length))
             (preorder-right
               (subseq preorder left-length)))
        (list root
              (tree-recovery preorder-left inorder-left)
              (tree-recovery preorder-right inorder-right)))
      (first preorder)))

For empty trees we return NIL. For trivial trees of one leaf node, we return a value.

For other trees, we first pop the root element from preorder (where it's first). Then we find a sublist starting with the root element in inorder. We use it to get a piece of inorder corresponding to our left subtree and a piece of inorder corresponding to our right subtree. Knowing the size of our left subtree, we get left and right piece of preorder easily.

Now when we have a tree, doing postorder traversal is easy:

(defun postorder (tree)
  (and tree ;; non-empty
       (if (consp tree) ;; non-leaf
           (destructuring-bind (root left right) tree
             (append (postorder left)
                     (postorder right)
                     (postorder root)))
           (list tree))))

Let's try:

(postorder 
 (tree-recovery '(a b d e c f)
                '(d b e a c f)))
=> (D E B F C A)

Seems to work.

Anton Kovalenko
  • 20,999
  • 2
  • 37
  • 69
  • does it work if the tree contains nodes with the same contents, trees with preorder like `(cons cons f nil cons 1 cons 2 cons 3 nil nil nil nil)? – Reb.Cabin Mar 23 '19 at 16:33
  • actually, it might even break on any nested cons trees like `(cons (cons x nil) nil)` – Reb.Cabin Mar 23 '19 at 21:12