Binary Trees in Python: Calculating Height of Tree

Рет қаралды 26,694

Күн бұрын

Пікірлер: 105

@karangupta6402 5 жыл бұрын

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 5 жыл бұрын

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

@waiyanleung5199 4 жыл бұрын

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 4 жыл бұрын

Cheers, and thanks for watching!

@LucidProgramming 4 жыл бұрын

@Daniel Kua Glad to hear it :)

@Rasheed-jf1gx 2 жыл бұрын

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

@LucidProgramming 2 жыл бұрын

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

@floyddsouza8855 2 жыл бұрын

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 2 жыл бұрын

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 2 жыл бұрын

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!

@sasukeuchiha5604 4 жыл бұрын

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 4 жыл бұрын

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

@qc4257 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

Hahaha, great compliment! :)

@ziaurrahman4187 2 жыл бұрын

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

@LucidProgramming 2 жыл бұрын

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 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

Thank you, Willian! :)

@JitendraKumar-br9lu 3 жыл бұрын

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

@LucidProgramming 3 жыл бұрын

Great to hear, no problem! :)

@devanshsolani2593 4 жыл бұрын

A simpler video and cleanest explanation!

@LucidProgramming 4 жыл бұрын

@AM-ml7dp 3 жыл бұрын

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

@LucidProgramming 3 жыл бұрын

@souljarohill8795 26 күн бұрын

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

@akakartik 3 жыл бұрын

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

@looneytoons2006 5 жыл бұрын

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

@LucidProgramming 5 жыл бұрын

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 KZbin page. bit.ly/lp_email

@jagdishwarbiradar1763 5 жыл бұрын

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 5 жыл бұрын

@@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 4 жыл бұрын

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 4 жыл бұрын

@jerrylin4980 3 жыл бұрын

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

@LucidProgramming 3 жыл бұрын

@rishikjasoriya 4 жыл бұрын

Wonderful Explanation Lucid!!

@LucidProgramming 4 жыл бұрын

@bactran7799 3 жыл бұрын

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 3 жыл бұрын

@bactran7799 3 жыл бұрын

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

@LucidProgramming 3 жыл бұрын

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

@gulshankataria2230 4 жыл бұрын

awesome explanation sir !!!

@LucidProgramming 4 жыл бұрын

@edgarlip2 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

Thank you! :)

@trackstr1 3 жыл бұрын

Great explanation!

@LucidProgramming 3 жыл бұрын

@NoorAli-uh4uq 5 жыл бұрын

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 5 жыл бұрын

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

@sutingyang9439 5 жыл бұрын

fantastic! I have watched all of your video

@LucidProgramming 5 жыл бұрын

Awesome, I hope they helped you out! :)

@xiaohaihuang4890 3 жыл бұрын

The best explanation!!!!!!

@LucidProgramming 3 жыл бұрын

@dillarakc651 5 жыл бұрын

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

@LucidProgramming 5 жыл бұрын

@dillarakc651 5 жыл бұрын

@@LucidProgramming I already subscribed :)

@LucidProgramming 5 жыл бұрын

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

@parthshah1563 2 жыл бұрын

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

@terranceoconnell5008 2 жыл бұрын

Thanks!

@LucidProgramming 2 жыл бұрын

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

@johnpeterantonio9016 4 жыл бұрын

so clear!!!

@LucidProgramming 4 жыл бұрын

Thank you! :)

@tejaspoojary5397 3 жыл бұрын

Thanks a lot!!

@LucidProgramming 3 жыл бұрын

@Roblox5091 4 жыл бұрын

life saver

@LucidProgramming 4 жыл бұрын

Thank you!

@anirvansen2941 5 жыл бұрын

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

@LucidProgramming 5 жыл бұрын

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

@jisuham7107 4 жыл бұрын

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 4 жыл бұрын

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

@chelloveck 6 жыл бұрын

thx

@LucidProgramming 6 жыл бұрын

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

@khavishbhundoo3792 6 жыл бұрын

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 6 жыл бұрын

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 6 жыл бұрын

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 6 жыл бұрын

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 6 жыл бұрын

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

@gothams1195 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

Looks fine to me on GitHub.

@gothams1195 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

@@gothams1195 Yeah...looks fine.

@LucidProgramming 4 жыл бұрын

@@gothams1195 Am I missing something?

@gothams1195 4 жыл бұрын

@@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))

@richybob6722 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

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

@arkyabagchi4791 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

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

@DoFlamingo_1P 4 жыл бұрын

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 4 жыл бұрын

Cool, thanks for sharing!

@chiragbansal2314 4 жыл бұрын

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

@sutingyang9439 5 жыл бұрын

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 5 жыл бұрын

Hmm, are you sure it's line 19?

@sutingyang9439 5 жыл бұрын

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

@LucidProgramming 5 жыл бұрын

No. That's why I am asking

@chaitanyatripathi1543 4 жыл бұрын

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

@LucidProgramming 4 жыл бұрын

You should probably look into Python classes.

@gothams1195 4 жыл бұрын

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 4 жыл бұрын

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

@Magmatic91 3 жыл бұрын

Wow great website, thanks for sharing !

@suthakark1816 4 жыл бұрын

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 4 жыл бұрын

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?