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
– kraskevich, Commented Feb 21, 2017 at 19:14

avysk · Accepted Answer · 2017-02-22 19:16:57Z

0

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

answered Feb 22, 2017 at 19:16

avysk

2,04514 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

segue_segway Over a year ago

This happens because, when I flatten root.left and set the pointer for root.right = flatten(root.left), root.right wasn't pointing to the root of the flattened left list?

avysk Over a year ago

Yes, exactly. Your recursive call expects flatten to return the root of the subtree it just flattened; however, flatten was not doing this.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related