# [Challenge] Build and Test Balance of a Binary Search Tree

Check out this site on asymptotic notation. Big O is just an upper bound for the runtime. Expressing the average case with big O is equally valid as expressing the worst case with it.

I’ll reply a bit later with the other questions when I get a chance to look at it properly.

Yes, the balance check is meant to run in that amount of time.

Only for the average case. The worst case is a sorted list, count how many steps are needed for any list [0, 1, 2, 3, … n]

This is possible, have a look at other people’s solutions above, they have used this approach.

Thanks.

Silly me. O(n log n) is off course true JUST for the balanced tree.

I apologize: I had been looking at other resources for potential solutions, when I got stuck, but @tagrockstar79958 solutions’ appears to use two objects as I desired.

1 Like

Can anybody tell me what the runtime for the .balanced() function of my BinarySearchTree is? I fear it is O(n2) and not O(n)? How could I adept it?

A muliplier is a constant, as in `O(Cn)`, but when the constant is removed, as is the case in Big-O, we’re left with `O(n)`.

I appreciate the answer, but does this mean you believe my solution runs in O(n)? Or does it mean, you thought I said O(2n)? Maybe, I should have said: O(n^2) or O(n)?

Sorry, I’m not entirely sure what the time complexity actually is. My comment only referred to constants being excluded. If there is a nested loop, then it is O(2^n), but if it is two consecutive loops, it is O(n).

Going to defer to a member better qualified in this area, @alexc.

class TreeNode:
def init(self, val):
self.val = val
self.left = None
self.right = None

class BinarySearchTree:
def init(self):
self.root = None

``````def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert_recursive(self.root, val)

def _insert_recursive(self, node, val):
if val < node.val:
if node.left is None:
node.left = TreeNode(val)
else:
self._insert_recursive(node.left, val)
else:
if node.right is None:
node.right = TreeNode(val)
else:
self._insert_recursive(node.right, val)

def print_tree(self):
self._print_tree_recursive(self.root, 0)

def _print_tree_recursive(self, node, level):
if node is not None:
self._print_tree_recursive(node.right, level + 1)
print("   " * level + str(node.val))
self._print_tree_recursive(node.left, level + 1)

def is_balanced(self):
return self._is_balanced_recursive(self.root) != -1

def _is_balanced_recursive(self, node):
if node is None:
return 0

left_depth = self._is_balanced_recursive(node.left)
right_depth = self._is_balanced_recursive(node.right)

if left_depth == -1 or right_depth == -1 or abs(left_depth - right_depth) > 1:
return -1

return max(left_depth, right_depth) + 1
``````

# Testing the Binary Search Tree

numbers = [10, 5, 15, 3, 7, 12, 18]
bst = BinarySearchTree()

for num in numbers:
bst.insert(num)

print(“Binary Search Tree:”)
bst.print_tree()

print(“\nIs the tree balanced?”, bst.is_balanced())