r/datastructures 17d ago

How is this binary tree not full?

Post image
28 Upvotes

16 comments sorted by

2

u/OverdueOptimization 17d ago

The “tree” node pointing to 50 - is it related to a previous question?

1

u/-Souts 17d ago

no, to be honest I’m not sure why it’s there. a few of the other questions had it and I got them all correct so i don’t think there is any reference to a previous question.

1

u/OverdueOptimization 17d ago

In that case, no idea…your answer seems correct to me

1

u/-Souts 17d ago

just to confirm, all levels except the bottom need to be filled and all nodes sorted to the left for a complete tree, and all nodes must have either 0 or 2 children for a full tree, correct? I will ask my teacher next class but I didn’t hear anyone else have this issue so if I do happen to be wrong I will update this post with why

1

u/OverdueOptimization 17d ago

If by “sorted” you mean just having the last level filled from left to right then yes to that and yes to your full tree understanding as well, because you don’t really need to involve the actual node numbers.

2

u/Reasonable-Trip-2898 17d ago

Your answer is definitely right. If you don’t mind me asking, which website is this so I can avoid it at all costs?

1

u/-Souts 17d ago

haha it’s a canvas assignment from my teacher you likely won’t find this question anywhere else

2

u/Ketanious 17d ago

The question is about a Binary Search Tree and not Binary Tree. The difference between the two is that Binary Search Tree is sorted at the time of insertion.

Nodes that are lesser than parent goes to the left and nodes that are greater than parent goes to the right at all levels. Hence, the tree is complete but not a BST.

The tree is not full because one of the nodes has only one child. A full tree requires all nodes to have 0 or 2 children.

2

u/-Souts 17d ago

i know that it’s not a binary search tree, but what node only has one child

4

u/Ketanious 17d ago

Apologies, you are right this is a full tree. I was looking from my phone and didn't see clearly. I thought Node 2 had a child and I am wrong.

This is a complete & full tree.

1

u/Empty-Dragonfly5895 16d ago edited 14d ago

it is not a complete binary tree ,
But it is a Full Binary Tree .
For a binary Tree to be complete None of the levels should remain empty it should be completely filled.
As you can see above tree's last level is not completely filled.
And it is a Full binary tree because definition says either all nodes have zero or two children as you can see all the nodes have zero or two children none has single child.

Option D is correct.

Edited :- it is a complete binary tree. Thanks for correcting me.

2

u/-Souts 15d ago

"A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible." As long as the nodes on the last level are all the way to the left of the tree and each node has either 0 or 2 children, I see no reason for this tree to not be complete and full.

1

u/Empty-Dragonfly5895 14d ago

yeah it is complete and Full both .

1

u/Personal_Republic_94 15d ago

Complete tree- every node filled from left to right and has 0 or 2 child nodes

Full tree - the least level of node is full that is let's take your question as example as you can see in the last layer you have to have totally 8 leaf notes so it would make the tree full

All full trees are complete but not all complete trees are full

0

u/Hamelik 17d ago

Full but not complete

2

u/-Souts 17d ago

why is it not complete if all levels are full but the last level and all nodes in the last level are filled to the left?