Binary search tree, number of nodes formula

In summary, the formula for the number of nodes in a typical binary search tree is 2^(n+1) - 1, where n is the depth of the tree. This is because the depth should be regarded as n=3, rather than n=4, as four represents the number of nodes in a path from root to tip, but three represents the number of "steps". This can be compared to the concept of a year, where there are two endpoints (t = 0 and t = 1) but it is still just one year.
  • #1
ducmod
86
0

Homework Statement


Hello!
Typical binary search tree has a number of nodes equal to 2^(n+1) - 1.
I don't understand why we add 1 to the n?
For example: a tree has a height 4.
#
# #
# # # #
# # # # # # # #
each level has 2^i nodes; i = 0, 2^0 = 1 for the first row, etc.
If the height is 4 then total amount of nodes is 15, which is 2^4 - 1,
and not 2^(4+1) - 1.

I would be grateful for your help!
 
Physics news on Phys.org
  • #2
ducmod said:

Homework Statement


Hello!
Typical binary search tree has a number of nodes equal to 2^(n+1) - 1.
I don't understand why we add 1 to the n?
For example: a tree has a height 4.
#
# #
# # # #
# # # # # # # #
each level has 2^i nodes; i = 0, 2^0 = 1 for the first row, etc.
If the height is 4 then total amount of nodes is 15, which is 2^4 - 1,
and not 2^(4+1) - 1.

I would be grateful for your help!

The formula works perfectly well if you regard the depth as n=3, rather than n=4. Four is the number of nodes in a path from root to tip, but three is the number of "steps". It is the same as saying that your first year of life has two endpoints, t = 0 and t = 1, but it is still just one year.
 
  • #3
Ray Vickson said:
The formula works perfectly well if you regard the depth as n=3, rather than n=4. Four is the number of nodes in a path from root to tip, but three is the number of "steps". It is the same as saying that your first year of life has two endpoints, t = 0 and t = 1, but it is still just one year.
I see now. Thank you!
 

FAQ: Binary search tree, number of nodes formula

1. How is the number of nodes in a binary search tree calculated?

The number of nodes in a binary search tree can be calculated using the formula N = 2^(h+1) - 1, where N is the number of nodes and h is the height of the tree.

2. Why is the number of nodes in a binary search tree important?

The number of nodes in a binary search tree is important because it gives us an idea of the size and complexity of the tree. It also helps us determine the efficiency of operations such as searching and inserting in the tree.

3. Is the number of nodes in a binary search tree always the same?

No, the number of nodes in a binary search tree can vary depending on the structure of the tree. However, for a given height h, the number of nodes will always be the same.

4. Does the number of nodes in a binary search tree affect its performance?

Yes, the number of nodes in a binary search tree can impact its performance. A larger number of nodes can result in slower search and insert operations, while a smaller number of nodes can lead to a more efficient tree.

5. Can the number of nodes in a binary search tree be negative?

No, the number of nodes in a binary search tree cannot be negative as it represents the actual number of nodes present in the tree. If the tree is empty, the number of nodes would be zero.

Similar threads

Replies
6
Views
2K
Replies
11
Views
1K
Replies
12
Views
3K
Replies
9
Views
2K
Replies
2
Views
1K
Replies
3
Views
3K
Back
Top