Question

What is the complexity of a balanced binary tree search? Complexity of searching one item in a balanced tree. The height of a balanced search tree is? Once is balanced there would a maximum height of the tree, what’s that? Explain in your own words.

Answer 1

The complexity of a balanced binary tree search is O(logn)

Explanation: When we traverse a binary search tree, we can go either left or right thus we remove one portion per traversing. So, the time complexity of log n is created.

The Complexity of searching one item in a balanced tree: O(logn)

Explanation: In a balanced tree, the worst-case scenario to search a number is O(logn) as we're eliminating a whole portion(either left or right) each time.

The height of a balanced search tree is: Log(n)

Eg: log(1) = 0

log(2) = 1

log(3) = 1

log(4) = 2

for balanced tree, total nodes are: 1, 3, 7 etc.

The height will be:   

for 1 node: log(1) = 0

for 3 node: log(1) = 1

for 7 node: log(1) = 2

Similarly, for a balanced tree with n nodes, the maximum height will be Log(n).