Return to Question

Consider this interview question:

Given a Node with a reference to a child, its next, its previous, and a variable for its value (1/2 tree, 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

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

Given a Node with a reference to a child, its next, its previous, and a variable for its value (1/2 tree, 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

def flatten(head):
    if not head: return head

    c = flatten(head.child) 
    n = flatten(head.next)
    if c:
        head.next = head.child
        head.child.prev = head
    if c and n:
        tail = c
        while tail.next:
            tail = tail.next
        tail.next = n
        n.prev = tail
    return head

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?

Consider this interview question:

Given a Node with a reference to a child, its next, its previous, and a variable for its value (1/2 tree, 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

def flatten(head):
    if not head: return head

    c = flatten(head.child) 
    n = flatten(head.next)
    if c:
        head.next = head.child
        head.child.prev = head
    if c and n:
        tail = c
        while tail.next:
            tail = tail.next
        tail.next = n
        n.prev = tail
    return head

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?

Given a Node with a reference to a child, its next, its previous, and a variable for its value (1/2 tree, 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

def flatten(head):
    if not head: return head

    c = flatten(head.child) 
    n = flatten(head.next)
    if c:
        head.next = head.child
        head.child.prev = head
    if c and n:
        tail = c
        while tail.next:
            tail = tail.next
        tail.next = n
        n.prev = tail
    return head

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?

Given a Node with a reference to a child, its next, its previous, and a variable for its value (1/2 tree, 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

def flatten(head):
    if not head: return head

    c = flatten(head.child) 
    n = flatten(head.next)
    if c:
        head.next = head.child
        head.child.prev = head
    if c and n:
        tail = c
        while tail.next:
            tail = tail.next
        tail.next = n
        n.prev = tail
    return head

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?