Today was the last day of classes. Danny gave us some topics to review for the exam and we took up a problem on one of the previous exams. The problem was to write a function which returns the head and tail of a doubly-linked list corresponding to an in-order traversal of a binary tree. I wasn't able to find the solution online, so I'll assume I shouldn't post it here. However, the solution was not so dissimilar in structure to this:
def inorder(node):
if not node:
return (None, None)
this = LLNode(node.data)
left_head, left_tail = inorder(node.left)
right_head, right_tail = inorder(node.right)
# do something (i.e. complete links between nodes)
return (left_head, right_tail)
For some reason, I thought that the solution would involve some sort of sandwiching structure. This is what I mean:
inorder()
# do something
inorder()
This is a typical inorder traversal algorithm, so I thought this was necessary to complete the function. Hence, the solution Danny gave seemed like a postorder traversal to me at first glance. After further inspection, I realized that the order of the recursive calls makes absolutely no difference. What does matter is in which order the nodes are linked. I verified this by coding up a preorder function. The function was almost identical in structure to the inorder function, but the node links were slightly different as I expected. It was nice to get this cleared up, since there was a very similar question in one of the labs which I remember I had completed, but I wasn't completely convinced with my solution.
Anyway, that's it for the course. It was great while it lasted.
Good luck on your exams!
