3 ms·
If I had to do this in production code I wouldn't do it that way (for a start I prefer static data structures where possible). I'd have 2 classes: BinaryTree an
by cabalamat 5y ago
If I had to do this in production code I wouldn't do it that way (for a start I prefer static data structures where possible). I'd have 2 classes: BinaryTree and DoubleLinkedList, each of which would have a constructor that takes a list as input, and a function that returns the data as a list:
class BinaryTree:
def __init__(self, data: List):
""" create from a list """
def asList(self)->List:
""" return my data as a list """
class DoubleLinkedList:
def __init__(self, data: List):
""" create from a list """
def asList(self)->List:
""" return my data as a list """
Then making a binary tree from a double-linked list is simply:
BinaryTree(dll.asList())
- Kranar 5y agoThat's fair but it's trivial to convert a BinaryTree to a LinkedList (doubly or singly). If you eliminate the requirement that this must be done in-place (which implies O(1) auxilliary space), then the solution is not particularly interesting. The practical use case for in-place algorithms is operating on large data sets that are directly on a disk. Think some kind of database organizing data directly on a hard drive. You want to avoid having to double the number of hard drives you need in order to do some kind of data transformation, and perform any linking/relinking directly on the disk.
- cabalamat 5y ago> That's fair but it's trivial to convert a BinaryTree to a LinkedList (doubly or singly) If there's a way of doing it that's trivial, and another way that's complex, I will do it the trivial way unless there's a very good reason to do it the complex way. > The practical use case for in-place algorithms is operating on large data sets that are directly on a disk. Think some kind of database organizing data directly on a hard drive. I just hope the system doesn't crash while it's in the middle of doing it!