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

HQ Announcements & Events
24

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.

25

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.

26

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
27

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?

28

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).

29

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)?

30

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.

31

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())

32

for the simple one
class Node:

def __init__(self, num):
    self.left = None
    self.right = None
    self.num = num

def insertNum(self, num):
    if num < self.num:
        if self.left is None:
            self.left = Node(num)  # Create a new Node with num and assign it to left
        else:
            self.left.insertNum(num)  # Recursively insert into the left subtree
    else:
        if self.right is None:
            self.right = Node(num)  # Create a new Node with num and assign it to right
        else:
            self.right.insertNum(num)  # Recursively insert into the right subtree

def printTree(root):
if root:
printTree(root.left)
print(root.num)
printTree(root.right)

A = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
root = Node(A[0]) # Initialize root with the first element of A
for num in A[1:]:
root.insertNum(num)

printTree(root)