Flatten Binary Tree --> Singly Linked List (Ruby)

Question

I'm working on a recursive algorithm to flatten a binary tree into a singly linked list. Problem statement:

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

I wrote the following recursive code that simply doesn't work (returns wrong answer), but I can't understand conceptually why not. Starting at the root, we flatten root.left and root.right. If root.left exists, then root.next (or in this case, root.right) will point to the flattened left list. Then, the left list points to the beginning of the right list. This continues recursively down the tree.

Is something wrong with this conceptually? I tried modeling it after a preorder traversal since essentially root is visited, then left, then right.

def flatten(root)
    return root if root.nil?
    left_list = flatten(root.left) 
    right_list = flatten(root.right)
    root.left = nil


    root.right = (left_list.nil? ? right_list : left_list)
    find_tail(left_list).right = right_list unless left_list.nil?
end

def find_tail(node)
    return nil if node.nil?
    until node.right.nil?
        node = node.right
    end

    node
end

What does "doesn't work" mean? Does it crash? Does it produce wrong output? Does it fail to terminate after a reasonable amount of time? — kraskevich

avysk avysk · Accepted Answer · 2017-02-22T19:16:57

Your flatten does not return what it should. It matters as you call it recursively. Change it to

    ...
    find_tail(left_list).right = right_list unless left_list.nil?
    root  # <-- add this line
end

Flatten Binary Tree --> Singly Linked List (Ruby)

1 Answers