We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.
Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
Next code requires O(n) memory:
deflevelOrder(self,root):q=[root]#i = 0#while i < len( q ):# current = q[i]# i += 1forcurrentinq:ifcurrent:print(current.data,end=' ')q.append(current.left)q.append(current.right)
Day 23: BST Level-Order Traversal
You are viewing a single comment's thread. Return to all comments →
The most "pythonic" way would be to use collections.deque.
Next code requires O(n) memory:
Edit: based on AbhishekVermaIIT's suggestion