Binary Trees in Python: Reverse Level-order Traversal

In this video, we go over how to perform a reverse level-order traversal in a binary tree. We then code up a solution in Python building on our binary tree class from the introduction video to this series.

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

Slides:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[davidrowlands]

Yet another excellent video. thank you

[jaideepmore]

Thid video was very much helpful Thanks.
I was wondering if we could do reverse order by using just a stack and came up with this solution:
def reverseorderPrint(self, start):
if start is not None:
stack = Stack()
stack.push(start)
i = 0
while i < stack.size():
node = stack.stack[i]
if node.left is not None:
stack.push(node.left)
if node.right is not None:
stack.push(node.right)
i += 1
i = stack.size() - 1
while i >= 0:
print(stack.stack[i])
i -= 1


Thought it might be helpful :)

[floyddsouza]

I got the answer by modifying your level-order traversal code. this code mod has a lower time complexity:

def reverse_levelorder_print (self, start):
if start is None:
return
L = queue()
L.enq(start)
traversal = ''
while L.length() >0:
traversal +=str(L.peek()) + '-'
node = L.deq()
if node.left:
L.enq(node.right)
if node.right:
L.enq(node.left)
return traversal[::-1]

[gothams]

Hey love your videos.I have a doubt, we are using the horizontal array as a queue(FIFO) right, then @4:12, we en-queued "4" first, then we are suppose dequeue 4"" first, why are we dequeuing"5" first, ....i mean we are using a queue like stack right ?

[vamsimanubolu]

Using Queue:

def reverseLevelorderTraversal(self, start):
Q=Queue()
Q.enque(start)
Traversal=' '
while Q.size()>0:
D=Q.deque()

if D.right is not None:
Q.enque(D.right)
if D.left is not None:
Q.enque(D.left)
return Traversal

[walid]

why you don't use the collections.deque and collections.queue ?

[priscaegbua]

Is there no difference between the stack class and the queue class beside the name of the methods? I think the peek method should be different, because the queue peek() should return the first item enqueued while the stack peek should return the last item. This is a bit confusing to me.

[samarasimhachalla]

Used 2 lists and came up with this. Hope it'll help somebody

def revlevorder(self, start):
if start is None:
return
l1 = []
l2 = []
l1.append(start)

while len(l1)>0:
l2.append(l1[0].data)
if l1[0].right:
l1.append(l1[0].right)
if l1[0].left:
l1.append(l1[0].left)
l1.pop(0)
return l2[::-1]

[sostomc]

What is the reason behind adding method size() and then calling it from __len__, other than just returning len(self.items) in __len__?

[undeadwolf]

using Linked List -

def rev_levelorder_trav(self, head_node):
trav = ''
ll = LinkedList()
ll.append(head_node)
x = ll.head
while x:
if x.data.right:
ll.append(x.data.right)
if x.data.left:
ll.append(x.data.left)
trav = '-{}'.format(x.data.value) + trav
x = x.next
return trav

[akshaykhadka]

when I added 6 and 7 to the binary tree, it's printing in this order:
4-5-6-7-2-3-1

[ghaith.seirawan]

Without Stack:

def reverse_level_order(self, root):
if root is None:
return
q = Queue( )
q.enqueue( root )
traversal = [ ]

while len ( q ) > 0:
traversal += str( q.peek( ) )
node = q.dequeue( )
if node.right:
q.enqueue( node.right )
if node.left:
q.enqueue( node.left )

traversal.reverse( )
return traversal

[agilc]

Thanks for the video, really helpful, but please try to add the time and space complexities in the next videos.

[rohanchakraborty]

Hii...I was getting the error as below:

Traceback (most recent call last):
File "C:/Users/dell/PycharmProjects/practice/bintr.py", line 158, in <module>

File "C:/Users/dell/PycharmProjects/practice/bintr.py", line 72, in print_tree
return
File "C:/Users/dell/PycharmProjects/practice/bintr.py", line 139, in reverse_levelorder_print
traversal += str(node.value) + "-"
AttributeError: 'NoneType' object has no attribute 'value'

[saisravankumar]

can you give the notes of these videos

[shrinandaggarwal]

what is the difference between postorder traversal and reverse order traversal?