Math for coding interviews/Tree levels and node counts
Binary Tree Height: Why Operations Are O(log n)
A balanced binary tree with n levels has about 2ⁿ nodes total. Conversely, if you have n nodes arranged as a balanced tree, the height (number of levels) is log₂(n). This relationship - height equals log(n) - is why balanced tree operations are so fast.
See it for yourself
A tree diagram. Level 0 has 1 node (root). Level 1 has 2 nodes. Level 2 has 4 nodes. Level 3 has 8 nodes. Total nodes = 1+2+4+8 = 15 = 2⁴-1. Height is 3 = log₂(15) rounded.
Tree levels and node counts
A balanced binary tree with n levels has about 2ⁿ nodes total. Conversely, if you have n nodes arranged as a balanced tree, the height (number of levels) is log₂(n). This relationship - height equals log(n) - is why balanced tree operations are so fast.
Think of it this way: An org chart. The CEO is at the top. Each manager has two direct reports. With 10 levels, there are over 1,000 employees - but you can reach any employee with at most 10 steps down the hierarchy.
For algorithms: BST search, insert, and delete are all O(log n) on a balanced tree. This is the logarithm story: height grows as log(n), so traversal steps stay small even for huge trees.
Real-world analogy
An org chart. The CEO is at the top. Each manager has two direct reports. With 10 levels, there are over 1,000 employees - but you can reach any employee with at most 10 steps down the hierarchy.
Why it matters in interviews
BST search, insert, and delete are all O(log n) on a balanced tree. This is the logarithm story: height grows as log(n), so traversal steps stay small even for huge trees.