Question

How to find maximum number of nodes in a binary search tree?

Answer 1

I am confused with this statement

The maximum number of nodes in a binary tree of depth kk is 2k−12k−1, k≥1k≥1.

How come this is true. Lets say I have the following tree

1 / \ 2 3

Here the depth of the tree. Here the depth of the tree is 1. So according to the formula, it will be 21−1=121−1=1. But we have 33 nodes here. I am really confused with this depth thing.

Any clarifications?