Consider this interview question:

Given a Node with a reference to a child, its next, its previous, and a variable for its value ($\frac{1}{2}$ tree, $\frac{1}{2}$ doubly linked list structure), you have to find a way to flatten the structure.

1 = 2 = 3 = 5
|       |
6 = 7   8
|
9


(reference down is child and reference across is next)

this above diagram becomes: 1 - 2 - 6 - 7- 9 - 3 - 5 - 8 but:

• 2 still has child reference to 6
• 7 still has child reference to 9
• 5 still has child reference to 8

Here is my code:

class Node(object):
def __init__(self, value, next_node=None, prev=None, child=None):
self.value = value
self.next = next_node
self.prev = prev
self.child = child

def __repr__(self):
return str(self.value)

one = Node(1)
two = Node(2)
three = Node(3)
five = Node(5)
six = Node(6)
seven = Node(7)
eight = Node(8)
nine = Node(9)
one.next = two
two.prev = one
two.next = three
two.child = six
three.prev = two
three.next = five
five.prev = three
five.child = eight
six.next = seven
seven.prev = six
seven.child = nine

if c:
if c and n:
tail = c
while tail.next:
tail = tail.next
tail.next = n
n.prev = tail

n = flatten(one)
while n:
print "%d -" % (n.value,),
n = n.next


I don't like the while loop. I could store tail and pass it around. Any better solution?

• Welcome on CodeReivew.SE! Out of curiosity, what is supposed to be the logic to flatten a structure which cannot be flatten in an obvious way? Is the stategy always to apply "child first" ? Also, you might want your Node class to handle the fact that when i.next is j then j.prev is i in order not to have to set the two relations manually. – SylvainD Jun 20 '14 at 12:29
• I found this interview question in the interwebz. I think we can assume that there are no cycles or any corner cases. Good idea with link function. – Lukasz Madon Jun 20 '14 at 12:54
• Why is the expected answer "1 - 2 - 6 - 7- 9 - 3 - 5 - 8" and not "1-2-3-5-8-6-7-9" – SylvainD Jun 20 '14 at 16:03

Your current implementation is quite nice.

The only way you are going to avoid using the while loop to find the right-most node is if you have each individual branch maintain its branch's tail Node. This is a [sort of] good approach to the problem. However, once you reach this point, a Node really starts becoming more than just a Node: it now has information about the entire structure instead of what is directly around it.

So instead of modifying the Node class, you could create a Tree class.

This change makes sense:

1. Right now you manually create your 'tree'. This approach is not very portable. A Tree class can handle its own creation.
2. You need to store information about the entire branch structure somewhere. Inside a Node doesn't feel right.
3. You don't really flatten a Node, you flatten a tree of nodes. Thus, it again makes sense to move the flatten function inside a Tree class (or at least take a Tree parameter).

Here is a skeleton version of my Tree class. I have stubbed out all my methods except flatten as that is the function in question:

class Tree(object):
def __init__(self, root=None):
self.root = root
self.tail = root
self.length = 1 if root else 0

def __iter__(self):
''' Allows iteration through the tree using for node in tree. '''
pass

def __getitem__(self, index):
''' Fetches the Node at the passed index. '''
pass

def grow(self, nodes):
''' Appends node/nodes/Tree onto itself. Be careful when adding Node
we need to append a *copy* of a Node, not the reference. '''
pass

def graft(self, tree, node_pos=0):
''' Grafts in another tree to this one. By default the new tree
is grafted to the root of the tree. '''
pass

def flatten(self):
''' Returns the flattened version of itself. '''
flat = Tree()
for next in self:
flat.grow(next)
if next.child:
flat.grow(next.child.flatten())
return flat


In this version of flatten, we keep the recursive feel as we call a method with the same method declaration. However, we are not doing true recursion because the methods are bound to different objects, and thus are different methods.

In any case, the flatten function is really quite simple:

1. Create the new Tree we are going to modify and return.
2. Loop through the Nodes of the current tree.
3. Append the current Node.

3.1. If that Node has a child Tree, append the flattened version of that Tree.

4. Return the final flattened Tree.

Here is my Tree class plus your Node class in action:

one, two, three, four, five, six, seven, eight, nine = [Node(num) for num in xrange(1,10)]

tree = Tree(one)
tree.grow([two, three, five])

# Graft the new Tree to the 3rd Node.
tree.graft(Tree(eight), 3)

branch = Tree(six)
branch.grow(seven)

# Graft the new Tree to the 1st Node.
branch.graft(Tree(nine), 1)

tree.graft(branch, 1)

def flatten(tree):
''' A non-class version of the flatten function. '''
flat = Tree()
for next in tree:
flat.grow(next)
if next.child:
flat.grow(flatten(next.child))
return flat

print ' - '.join([str(node.value) for node in flatten(tree)])
print ' - '.join([str(node.value) for node in tree.flatten()])