Binary Trees in Python: Calculating Height of Tree

[@karangupta6402]

Every time I watch your video, I always leave a comment. I don't have enough words to appreciate your work and the videos that you are delivering :)
Thank you for the remarkable contents :)

[@LucidProgramming]

I really appreciate those words. Thank you, and I'm happy to hear that the channel has been useful to you!

[@waiyanleung5199]

This is the only video makes me understand how the recursion's done. I've been studying all the relevant materials on the web for hours. None's as clear as this video. Thank you so much teacher!

[@LucidProgramming]

Cheers, and thanks for watching!

[@LucidProgramming]

@Daniel Kua Glad to hear it :)

[@floyddsouza8855]

You are very good. I was lost in your previous video on 'in order traversal' as to how the recursion goes back up the tree after coming down. I finally understand from this video. Thank you for the great work you do.

[@tabhashim3887]

I just want to let you know that you are such a good teacher. After watching a couple of your videos, I am able to look at the theory and then code up the implementation (or get really close to doing so) on my own thanks to your clear-cut instructions on the videos prior to this one. YOU ARE AMAZING!!!

[@LucidProgramming]

Hi Tab. Thank you so much for the kind words. I sincerely appreciate them and want to thank you for your words of encouragement and support. Cheers, and thank you for watching!

[@Rasheed-jf1gx]

Even after 3 years i couldnt find anyone could make it clear more Than You

[@LucidProgramming]

That's wonderful to hear! Thank you for the kind words!

[@sasukeuchiha5604]

This made me understand recursion like a gem , man u truly saved my day and your videos are top notch and no other content in youtube is as clear as your's

[@LucidProgramming]

Glad to hear it! If you like the content, please do subscribe!

[@ziaurrahman4187]

your lectures are very explainatory...and i understand the idea of recursion from this video.
Thank's for such a explanatory videos.

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@williandougherty]

The best explanation strategy that I've already seen. Thank you a lot.

[@LucidProgramming]

Thank you, Willian! :)

[@JitendraKumar-br9lu]

now I got these concepts after watching many videos. Thanks sir😇

[@LucidProgramming]

Great to hear, no problem! :)

[@devanshsolani2593]

A simpler video and cleanest explanation!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@akakartik]

Gold, have been searching a video for this kind of explanation, thank you so much

[@AM-ml7dp]

Literally the best explanation out there!!!!!!!!!!!!!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@qc4257]

this playlist is a feast for hungry developers who want to learn 🔥

[@LucidProgramming]

Hahaha, great compliment! :)

[@jerrylin4980]

I've watched about 10 videos and still couldn't understand. Thank you so much!!!!!!!!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@souljarohill8795]

Not a hard problem at all in just understanding it and the solution is very simple as well. However I must admit this is the type of problem I feel like you wouldn’t understand how to solve unless you have seen it before, failed, then looked at the solution. Maybe I’m just not good enough I’ll accept that. Or I don’t understand trees as much as I thought I do. I just find it hard to believe most would know how to solve it without first failing. The trick for the max never crossed my mind. The way I would have solved it at first was to long and I knew wasn’t right. I thought about always spliting up right and left pointers of the sub tree and kept incrementing the height but knew instantly that wouldn’t work and become to complicated. Great video appreciate you breaking it down

[@looneytoons2006]

amazingly explained thank you so much.
i have any trouble with understanding recursion, this example was great tnx

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing!
I really appreciate the support, and if you want to support the channel, I do have a PayPal link (www.paypal.me/VincentRusso1) for donations that go directly to the creation of content on this channel.
I hope that the content I provide there will enhance the videos on my UA-cam page.
bit.ly/lp_email

[@jagdishwarbiradar1763]

trouble in this recursion , can you please explain at video time(9:25) to (9: 35) ,how end node go to upper node(2) and then directly right node ?

[@LucidProgramming]

@@jagdishwarbiradar1763 Check out that playlist I shared with you in the other video. I think that might clear some things up. Cheers, and thanks again!

[@chakshuprajapati698]

Thank you so much for this entire series , Great explanation and pretty good implementation , It's very hard to find data structures implementation in python . Again thank you for making this whole series ❤️.

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@terranceoconnell5008]

Thanks!

[@LucidProgramming]

Thank you so much for the kind donation, Terrance! I sincerely appreciate your support!

[@rishikjasoriya]

Wonderful Explanation Lucid!!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@bactran7799]

thanks a lot Lucid, this is the best video explaining BST that I've ever seen. Thumps up and subcribes. pls keep your great works

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@bactran7799]

@@LucidProgramming thanks Lucid, I did subscribe and always click the link of ads that pop up on your videos. Cheers

[@LucidProgramming]

@@bactran7799 Very much appreciate the support, thank you!

[@trackstr1]

Great explanation!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@gulshankataria2230]

awesome explanation sir !!!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@edgarlip2]

one of the best ! if not the best itself !!!!

[@LucidProgramming]

Thank you! :)

[@xiaohaihuang4890]

The best explanation!!!!!!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@sutingyang9439]

fantastic! I have watched all of your video

[@LucidProgramming]

Awesome, I hope they helped you out! :)

[@arkyabagchi4791]

at 9:33 how you move back from node 4 to node 2 it is really confusing for me to understand

[@LucidProgramming]

What about that is confusing, could you give more context?

[@NoorAli-uh4uq]

We can also this two functions but yours is much simple and efficient.
def height(self):
if self.root is not None:
return self._height(self.root, 0)
else:
return 0
def _height(self, curr_node, curr_height): # helper function
if curr_node is None:
return curr_height
left_height = self._height(curr_node.left_child, curr_height + 1)
right_height = self._height(curr_node.right_child, curr_height + 1)
return max(left_height, right_height)

[@LucidProgramming]

Yep, that looks like it does the job. Cheers, and thanks for sharing!

[@dillarakc651]

Thank you very much for the nice presentation. God bless you. We expect more videos from you. please help us.

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing!
I really appreciate the support, and if you want to support the channel, I do have a PayPal link (www.paypal.me/VincentRusso1) for donations that go directly to the creation of content on this channel.
I hope that the content I provide there will enhance the videos on my UA-cam page.
bit.ly/lp_email

[@dillarakc651]

@@LucidProgramming I already subscribed :)

[@LucidProgramming]

@@dillarakc651 Awesome, thank you for the support! :)

[@parthshah1563]

Hi LucidProgramming,
I'm always confused when to use return 0 and return -1 in BASE condition. I'll appreciate it if you can explain me why you have not used return 0.
Thank you

[@johnpeterantonio9016]

so clear!!!

[@LucidProgramming]

Thank you! :)

[@tejaspoojary5397]

Thanks a lot!!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@Roblox5091]

life saver

[@LucidProgramming]

Thank you!

[@anirvansen2941]

Hi amazing content, can you please tell when can we expect videos on graph data structures?

[@LucidProgramming]

Thanks! I can't say exactly when, but it's on my to-do list! Cheers, and stay tuned!

[@jisuham7107]

Can I ask a question? With this code, is it possible to update all the nodes' height? For example, if I insert or delete any node, some nodes' height will be changed. In this case, if I use this height function after inserting or deleting node, will it be able to update all the nodes' height?

[@LucidProgramming]

Yes, that's possible. Why wouldn't that be?

[@gothams1195]

Hey , the code for inorder_iterative and postorder_iterative are same in the github link provided in THIS video.

[@LucidProgramming]

Looks fine to me on GitHub.

[@gothams1195]

@@LucidProgramming github.com/vprusso/youtube_tutorials/blob/master/data_structures/trees/binary_trees/binary_tree_height.py

[@LucidProgramming]

@@gothams1195 Yeah...looks fine.

[@LucidProgramming]

@@gothams1195 Am I missing something?

[@gothams1195]

@@LucidProgramming class Stack(object):
def __init__(self):
self.items = []
def __len__(self):
return self.size()

def size(self):
return len(self.items)
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def __str__(self):
s = ""
for i in range(len(self.items)):
s += str(self.items[i].value) + "-"
return s
class Queue(object):
def __init__(self):
self.items = []
def __len__(self):
return self.size()
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
if not self.is_empty():
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return len(self.items) == 0
def peek(self):
if not self.is_empty():
return self.items[-1].value
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree(object):
def __init__(self, root):
self.root = Node(root)
def search(self, find_val, traversal_type):
if traversal_type == "preorder":
return self.preorder_search(tree.root, find_val)
elif traversal_type == "inorder":
return self.inorder_search(tree.root, find_val)
elif traversal_type == "postorder":
return self.postorder_search(tree.root, find_val)
else:
print("Traversal type " + str(traversal_type) + " not recognized.")
return False
def print_tree(self, traversal_type):
# Recursive traversals
if traversal_type == "preorder":
return self.preorder_print(tree.root, "")
elif traversal_type == "inorder":
return self.inorder_print(tree.root, "")
elif traversal_type == "postorder":
return self.postorder_print(tree.root, "")
# Iterative traversals
elif traversal_type == "levelorder":
return self.levelorder_print(tree.root)
elif traversal_type == "inorder_iterative":
return self.inorder_iterative(tree.root)
elif traversal_type == "preorder_iterative":
return self.preorder_iterative(tree.root)
elif traversal_type == "postorder_iterative":
return self.postorder_iterative(tree.root)
else:
print("Traversal type " + str(traversal_type) + " not recognized.")
return False
def levelorder_print(self, start):
if start is None:
return
queue = Queue()
queue.enqueue(start)
traversal = ""
while len(queue) > 0:
traversal += str(queue.peek()) + "-"
node = queue.dequeue()
if node.left:
queue.enqueue(node.left)
if node.right:
queue.enqueue(node.right)
return traversal
def preorder_search(self, start, find_val):
if start:
if start.value == find_val:
return True
else:
return self.preorder_search(start.left, find_val) or \
self.preorder_search(start.right, find_val)
return False
def preorder_print(self, start, traversal):
"""Root->Left-Right"""
if start:
traversal += (str(start.value) + "-")
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
def inorder_print(self, start, traversal):
"""Left->Root->Right"""
if start:
traversal = self.inorder_print(start.left, traversal)
traversal += (str(start.value) + "-")
traversal = self.inorder_print(start.right, traversal)
return traversal
def postorder_print(self, start, traversal):
"""Left->Right->Root"""
if start:
traversal = self.postorder_print(start.left, traversal)
traversal = self.postorder_print(start.right, traversal)
traversal += (str(start.value) + "-")
return traversal
def preorder_iterative(self, start):
stack = Stack()
cur = start
is_done = False
traversal = ""
while not is_done:
if cur is not None:
traversal += str(cur.value) + "-"
stack.push(cur)
cur = cur.left
else:
if len(stack) > 0:
cur = stack.pop()
cur = cur.right
else:
is_done = True
return traversal
def inorder_iterative(self, start):
s = Stack()
cur = start
is_done = False
traversal = ""
while not is_done:
if cur is not None:
s.push(cur)
cur = cur.left
else:
if len(s) > 0:
cur = s.pop()
traversal += str(cur.value) + "-"
cur = cur.right
else:
is_done = True
return traversal
def postorder_iterative(self, start):
s = Stack()
cur = start
is_done = False
traversal = ""
while not is_done:

if cur is not None:
s.push(cur)
cur = cur.left
else:
if len(s) > 0:
cur = s.pop()
traversal += str(cur.value) + "-"
cur = cur.right
else:
is_done = True
return traversal
def height(self, node):
if node is None:
return -1
left_height = self.height(node.left)
right_height = self.height(node.right)
return 1 + max(left_height, right_height)
# Calculate height of binary tree:
# 1
# / \
# 2 3
# / \
# 4 5
#
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
print(tree.height(tree.root))

[@chelloveck]

thx

[@LucidProgramming]

No problem, Сергей, happy to help! Cheers, and thanks for watching!

[@khavishbhundoo3792]

The traversal used here is a post order one correct? .Also I think we can keep track of the height of the tree in the class rather than recalculating it every time

[@LucidProgramming]

Hi Khavish. You are absolutely correct, the traversal used in this video is post-order. Certainly, you could use the same approach with any of the other traversal algorithms as well, post-order was just selected more-or-less by default for this video.
With respect to your section question, you most certainly could keep a class variable to keep track of the height. I suppose the reason I am not doing that here is that calculating the height of a tree that you do not have a class variable for is a fairly common interview problem. Also, I think calculating the height is a somewhat non-trivial showcase of recursion in action, so I wanted to explicitly show that in this video. In practice though, you're spot on! Cheers, and thanks for the comment.

[@khavishbhundoo3792]

I get aim of the video and i am certainly appreciate the quality of your videos.I also notice that you defined the height of tree as the longest number of edges from the root to a leaf, it could be number of nodes as well rather than edges imho.

[@LucidProgramming]

Hi Khavish. Right, thanks for the comment on quality. I'm always trying to improve the content, so I appreciate any and all feedback. Regarding the height definition though, I would disagree. I'm basing my definition of height on the Wikipedia definition, which also appears to be the one in CLRS. If you define it based on the number of nodes in the path, you will obtain off-by-one height values. Definitions should not be an opinion-based matter, but should be concrete! :)

[@khavishbhundoo3792]

I managed to code the height calculation iteratively @ repl.it/repls/InterestingHumiliatingWordprocessing . It is based on the definition in CLRS and thanks again for your time.Hoping to see a video on AVL trees soon.Kind Regards

[@sutingyang9439]

In the line 19, why not just return 0 and in the last one return max(left_height, right_height)? I have tried that out, doesn't work

[@LucidProgramming]

Hmm, are you sure it's line 19?

[@sutingyang9439]

@@LucidProgramming I am sorry. But do you know what line I am indicating ?

[@LucidProgramming]

No. That's why I am asking

[@richybob6722]

What is the time complexity of this code? If this isn't constant time how would you do it in constant time?

[@LucidProgramming]

Storing the height as you add nodes would suffice. That would be constant time.

[@DoFlamingo_1P]

I tried non iterative approach is this correct..
from collections import deque
def height(root):
if root is None:
return 0
left = 0
right = 0
d = deque()
d.append(root)
depth = 0
while len(d) != 0:
node = d.popleft()
depth = max(left, right)
if node.left is not None:
d.append(node.left)
left += 1
if node.right is not None:
d.append(node.right)
right += 1
return depth

[@LucidProgramming]

Cool, thanks for sharing!

[@chiragbansal2314]

Hello Dhruv and sir. Will these iterative solution work for non balanced tree? I think it won't work but please correct me if am wrong. Thank you

[@chaitanyatripathi1543]

why are we writing "self.height(node.left)" height is a function why are we using self keyword?

[@LucidProgramming]

You should probably look into Python classes.

[@suthakark1816]

class Stack(object):
def __init__(self):
self.lst=[]
def push(self,data):
self.lst.append(data)
def pop(self):
if not self.empty():
return self.lst.pop()
def empty(self):
return self.lst==[]
def __len__(self):
return self.size()
def size(self):
return len(self.lst)
class Queue(object):
def __init__(self):
self.items=[]
def enqueue(self,item):
self.items.insert(0,item)
def dequeue(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1].value
def is_empty(self):
return self.items==[]
def __len__(self):
return self.size()
def size(self):
return len(self.items)
class Node(object):
def __init__(self,value):
self.value=value
self.right=None
self.left=None
class BinaryTree(object):
def __init__(self,data):
self.root=Node(data)
# Preorder Traversal
#
# Root-->Left-->Right
#
#
# 2
# / \
# 4 3
# / \ \
# 6 8 5
#
# PreOrder: 2->4->6->8->3->5
#
# InOrder Traversal
#
# Left-->Root-->Right
#
# InOrder: 6->4->8->2->3->5
#
# PostOrder Traversal
#
# Left-->Right-->Root
#
# PostOrder: 6->8->4->5->3->2
#
# Level Order: Fill the elements level by level
#
# LevelOrder: 2->4->3->6->8->5
#
#
def preorder_print(self,start,traversal):
if start:
traversal+=(str(start.value)+"-")
traversal=self.preorder_print(start.left,traversal)
traversal=self.preorder_print(start.right,traversal)
return traversal
def inorder_traversal(self,start,traversal):
if start:
traversal=self.inorder_traversal(start.left,traversal)
traversal+=(str(start.value)+"-")
traversal=self.inorder_traversal(start.right,traversal)
return traversal
def postorder(self,start,traversal):
if start:
traversal=self.postorder(start.left,traversal)
traversal=self.postorder(start.right,traversal)
traversal+= str(start.value)+"-"
return traversal
def levelorder(self,start):
if start is None:
return
traversal=""
queue=Queue()
queue.enqueue(start)
while len(queue)>0:
traversal+=str(queue.peek()) +"-"
node=queue.dequeue()
if node.left:
queue.enqueue(node.left)
if node.right:
queue.enqueue(node.right)
return traversal
def reverse_levelorder(self,start):
if not start:
return
traversal=""
queue=Queue()
queue.enqueue(start)
stack=Stack()
while len(queue)>0:
node=queue.dequeue()
stack.push(node)
if node.right:
queue.enqueue(node.right)
if node.left:
queue.enqueue(node.left)
while len(stack)>0:
node=stack.pop()
traversal+=str(node.value)+"-"
return traversal

def height(self,node):
if node is None:
return -1
left_height=self.height(node.left)
right_height=self.height(node.right)
return 1+max(left_height,right_height)

def printer(self,traversal_type):
if traversal_type=="preorder":
return traversal_type+" "+self.preorder_print(self.root,"")
elif traversal_type=="inorder":
return traversal_type+" "+self.inorder_traversal(self.root,"")
elif traversal_type=="postorder":
return traversal_type+" "+self.postorder(self.root,"")
elif traversal_type=="levelorder":
return traversal_type+" "+self.levelorder(self.root)
elif traversal_type=="reverselevelorder":
return traversal_type+" "+self.reverse_levelorder(self.root)

tree=BinaryTree(2)
tree.root.right=Node(3)
tree.root.left=Node(4)
tree.root.right.right=Node(5)
tree.root.left.left=Node(6)
tree.root.left.right=Node(8)

[@LucidProgramming]

Why did you post this as a comment? There doesn't seem to be any context as to why you posted this. Is this your implementation?

[@gothams1195]

Dude Seriously love your videos. I also use www.pythontutor.com to trace recursion. Maybe you want to use , while explaining , people may like it.

[@LucidProgramming]

Cool, thanks for the tip and for the kind words!

[@Magmatic91]

Wow great website, thanks for sharing !

[@divyanshurana2043]

600th like :)