+ 2

# Is there any way to represent a binaary tree as singly linked list

I was asked this question in an interview how will you represent a binary tree as linked list(singly) , i still havent figured out.. plese help me

2 Respostas

+ 4

If a singly linked list only has one outgoing link I don't think it is possible to do this while maintaining the tree structure. Of course you could probably serialize the tree via a depth or breadth first traversal but then you would lose the tree structure.

+ 3

You can always traverse a binary tree in ascending order of elements, because the left node is always smaller than the right. So I think that would be a way to start from the smallest element (first go left until you reach a leaf) and 'collect' all leafs into the singly linked list on ascending order. Reversing this process does not seem possible though (from list back to the same binary tree).