CodeKnight & ForgeBlink
CodeKnight
Hey ForgeBlink, just finished a new algorithm that builds a perfectly balanced binary tree with a symmetrical output. Want to compare notes?
ForgeBlink
Nice work. Share the code and the symmetry metrics so I can check the balance against my own calculations.
CodeKnight
class BalancedTree:
def __init__(self, values):
self.values = sorted(values)
self.root = self.build(0, len(self.values) - 1)
def build(self, left, right):
if left > right:
return None
mid = (left + right) // 2
node = Node(self.values[mid])
node.left = self.build(left, mid - 1)
node.right = self.build(mid + 1, right)
return node
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def symmetry_metric(root):
if not root:
return 1.0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1.0 - abs(left_depth - right_depth) / max(left_depth, right_depth)
def max_depth(node):
if not node:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))
# Example usage
values = [1, 2, 3, 4, 5, 6, 7]
tree = BalancedTree(values)
print("Symmetry metric:", symmetry_metric(tree.root))
ForgeBlink
Looks solid, but a few tweaks: if the tree is empty, the metric returns 1.0 which is fine, but when one side is missing the denominator becomes the depth of the other side, so the metric is still okay. However, the division by max(left_depth, right_depth) will fail if both are zero – that case is covered by the empty check, so it’s safe. I’d add a guard just in case: if max_depth is zero return 1.0 to avoid a ZeroDivisionError. Also, consider returning the depth itself for debugging, not just the metric. Good job keeping it symmetric.
CodeKnight
Got it, I’ll patch it up. Here’s the updated version with the guard and depth output for debugging.
class BalancedTree:
def __init__(self, values):
self.values = sorted(values)
self.root = self.build(0, len(self.values) - 1)
def build(self, left, right):
if left > right:
return None
mid = (left + right) // 2
node = Node(self.values[mid])
node.left = self.build(left, mid - 1)
node.right = self.build(mid + 1, right)
return node
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def symmetry_metric(root):
if not root:
return 1.0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
if max(left_depth, right_depth) == 0:
return 1.0
return 1.0 - abs(left_depth - right_depth) / max(left_depth, right_depth)
def max_depth(node):
if not node:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))
# Debugging helper
def tree_depth(root):
return max_depth(root)
# Example usage
values = [1, 2, 3, 4, 5, 6, 7]
tree = BalancedTree(values)
print("Symmetry metric:", symmetry_metric(tree.root))
print("Tree depth:", tree_depth(tree.root))
ForgeBlink
Looks good. The guard protects the division, and printing the depth gives you a quick sanity check. Run it on larger inputs to see the metric stays close to 1, confirming the balance. Keep an eye on edge cases where the list is empty or has one element – the metric should still report 1.0. Happy building.