Master advanced binary tree operations including recursive search, level-first traversal, and depth-first traversal techniques.
class BinaryTree:
def __init__(self, root=None):
self.root = root
def search(self, value):
return self._search_recursive(self.root, value)
def _search_recursive(self, node, value):
# Base cases
if node is None:
return None
if node.value == value:
return node
# Recursive cases
left = self._search_recursive(node.left, value)
if left:
return left
return self._search_recursive(node.right, value)
def level_order_traversal(root):
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
class BinaryTree:
def __init__(self, root=None):
self.root = root
# In-order traversal
def in_order(self):
result = []
self._in_order_recursive(self.root, result)
return result
def _in_order_recursive(self, node, result):
if node:
self._in_order_recursive(node.left, result)
result.append(node.value)
self._in_order_recursive(node.right, result)
# Pre-order traversal
def pre_order(self):
result = []
self._pre_order_recursive(self.root, result)
return result
def _pre_order_recursive(self, node, result):
if node:
result.append(node.value)
self._pre_order_recursive(node.left, result)
self._pre_order_recursive(node.right, result)
Implement a function to find the maximum depth (height) of a binary tree.
Implement a function that returns an array where each element is the sum of values at that level.
3
/ \
9 20
/ \
15 7
Output: [3, 29, 22] // Level sums
Implement a function that traverses the tree in a zigzag pattern.
3
/ \
9 20
/ \
15 7
Output: [3, 20, 9, 15, 7] // Zigzag pattern
Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are excellent for practicing binary tree traversal techniques.