Problem statement

https://binarysearch.com/problems/Linked-List-to-ZigZag-Tree-Path/

Solution

Traverse list and attach nodes to the left or to the right.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, node):
        if not node: return None
        root = curr = Tree(node.val)
        while node.next:
            if node.next.val < node.val:
                curr.left = Tree(node.next.val)
                curr = curr.left
            else:
                curr.right = Tree(node.next.val)
                curr = curr.right
            node = node.next
        return root