I got a java test done and somehow my answer for this question is incorrect, can you guys help me explain it?
So the question is: in a binary tree with height 3 the least deep leaf has depth 2 (Root has depth 0).
a)Max numbers of nodes this tree can have?
b) Min numbers of nodes this tree can have?
My answer is 7 and 4, yet my professor said it should be 13 and 5
Ask him to draw it for you.
I did, and I now know that height of 3 mean 4 level total, wat confused me was least deep leaf has depth 2. Why so, it should be depth 3 if height is 3.
wat confused me was least deep leaf has depth 2. Why so, it should be depth 3 if height is 3.
No, it shouldn't, there's a difference between depth of a node and height of a tree.
The depth of a node is the number of edges on the path from the root node to that node.
The height of a tree is the length of a longest path from the root node to a leaf node.
However if your tree height is 3, then the leaf node on a longest path has depth 3.
wat confused me was least deep leaf has depth 2. Why so, it should be depth 3 if height is 3.
It means the leaf that's not at the deepest level (level 3, matching the height). In this case, 7 in the following tree is the "least deep" leaf. The height is 3, the least deep leaf is at level 2, and the tree is as full as it can be, so it's the answer to part a of your question:
1
2 3
4 5 6 7
8 9 a b c d
That's 13 nodes, on the assumption that the height excludes the root. However, if the root is at depth 0 then that's more of a safe assumption than usual. For the minimum you need to recognize that the tree isn't required to be full or complete, and the smallest tree possible while maintaining the two restrictions (a height of 3 and the least deep leaf at level 2) is some variation of this:
1
2
3 4
5
The height is still 3, the least deep leaf is still at level 2, and the tree cannot have fewer than 5 nodes without breaking one of those two invariants.
I see, so the leaf thing @ lvl 2 is a constraint. But without it, I can safely say the min numbers of nodes is 4, correct?
But without it, I can safely say the min numbers of nodes is 4, correct?
If you're changing the rules then remove the other constraint and the minimum number of nodes is zero.
Thank you, I finally understand it!
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.