Binary Trees in Python: Calculating Size of Tree

In this video, we will continue to build on our binary tree class from previous videos. Specifically, we will show how to calculate the size of a binary tree.

The "size" of a binary tree is the total number of nodes present in the binary tree. We will explicitly define this quantity in greater detail and cover a strategy for how one may calculate this quantity in the binary tree data structure we have been building in this series of videos.

The entire binary trees playlist can be found here:

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:

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

[XAaronJadeX]

Awesome teaching! I really like the way you teach :) I'm so glad to be your student. Just finishing this series and waiting for more!

[aditya]

Thank you! The content from your data structures and algorithms playlist is really helpful for me.
Subscribed!

[mdarifulislamsourov]

Peace be upon you brother. Nice to have you and your lectures by the grace of almighty. May Allah bless you and strengthen you to make this kind of helpful content for us.

[suthakark]

*Hey I think there is no need of using stack here*
Instead you can do the following..


def size(self, node):
if node is None:
return 0


return 1+(left_size+right_size)


*I wrote this code myself only after seeing your all lectures, the credits goes to you LUCID*
You made me to write code myself love you man

[LordSunLight]

Well, isn't that some timing. Am studying IT and this is one of the topics in my upcoming exams :D

[rahls]

Hey, do you plan on the add more videos in this series?
I absolutely love your content man. Thank you so much.
Would be nice to see more problems on BST and then maybe some advanced data structures like Red Black tree, hash tables, etc.

[simonchen]

Hi, thx for making this video. In the ppt, you use a queue model to show the concept of this, in the code you code them in stack. And since you pop the element out right after you push it in, stack or queue (FIFO OR LIFO) doesn't really matter. Could use recursive as well.

[galgal]

Hello, shouldn' t the stack data structure be called queue at the iterative approach, because it pops elements from the front and adds elements to the back?
Also, thank you so much for the great videos!

[NoorAli-uhuq]

Amazing content as usual, I have one question I have a project on AVL trees which is a special type of Binary Trees did you made any video about that?

[elachichai]

Great video.
Could you add one for binary heap/priority queue as well? and Graph algos?

[rupsh]

I've been loving this series so far...can you also explain views of trees

[jonarmani]

It wasn't until you passed "tree.root" into the size_() function at the very end did I realize: The benefit of size_() over size() is that you can measure the size of a sub-tree within the tree, using:
*print( tree.size_(tree.root.left) / tree.size_(tree.root.right) )*
^ This tells you the tree is 3.0x heavier on the left than the right. This lines up with your diagram.

[piyush]

Thank you for posting these helpful videos!
I'm trying to solve a problem on LeetCode and it asks to find the deepest subtree in the binary tree.
I have implemented the code below but it is returning every node whose height is 1.

def height_2(self, root_node):
if root_node is None:
return -1

left_height = self.height_2(root_node.left)
right_height =

#This is where the deep check is made and the node value is added to the global list called "deepest"
if (min(left_height, right_height) + 1) == 1:

print(self.deepest)


return 1 + max(left_height, right_height)

# THE BINARY TREE STRUCTURE
#
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
# / \
# 8 9

The answer should be [5] because it is the root node of the deepest subtree but the result returns [5, 2, 3]

[ankurjay]

At 2:05, and onwards, by 'stack' you mean a queue, right? Because the way the data is inserted and popped off, looks like a Queue (FIFO)

[rohanchakraborty]

Hii..I dont know how..but I am not getting output in the "reverse order traversal video"..Its saying "Non-type Object has no attribute ''value" "

[chanlarry]

Hi, I am following all your step to code and I get error I don't know why:
'NoneType' object has no attribute 'left'
It seems that when I push the root in stack, the root is a Nonetype object. However I have already created the tree like you do in video.
I am so confused :(

[VikramKumar-tkwg]

Sir can we solve this problem using iterative approach as well?

[TahirHoxha]

def treeSize(self, tree, count = 0):
if tree:
count += 1
count = self.treeSize(tree.left, count)
count = self.treeSize(tree.right, count)

return count

[AMIKETcestionsGAURAV]

I am following all your videos on data structure. I liked all your videos so far. I wrote the code to find the size of the tree with queue implementation. Please let me know if my implementation is wrong:

def size_levelOrderTraversal(self, current):
count = 0
if current is None:
return


queue = Queue()
queue.enqueue(current)


while Queue.size(queue) > 0:
count += 1
node = queue.dequeue()
if node.left is not None:
queue.enqueue(node.left)
if node.right is not None:
queue.enqueue(node.right)
return count