Standardmäßig ist der Prompt ausgewählt, der zuerst die Quelle prüft. Sie können zu einem direkten Befehl wechseln oder eine lokale Kopie herunterladen.
Quelldateien prüfen
Lesen Sie SKILL.md und alle von SkillsMP angezeigten Begleitdateien, bevor Sie sich für eine Installation entscheiden.
Mit Codex oder Claude installieren Kopieren Sie diesen Prompt, fügen Sie ihn in Codex, Claude oder einen anderen Assistant ein und lassen Sie die Skill-Seite prüfen und installieren.
Ein direkter Befehl überspringt den Prüf-Prompt. Prüfen Sie die Quelle, bevor Sie ihn ausführen.
{"inorder":{"time":"O(n)","space":"O(h) recursive, O(n) iterative worst"},"preorder":{"time":"O(n)","space":"O(h)"},"postorder":{"time":"O(n)","space":"O(h)"},"level_order":{"time":"O(n)","space":"O(w) where w = max width"}}
Tree Traversal Skill
Atomic Responsibility: Execute tree traversal algorithms with correct order and optimal space.
Tree Node Definition
from typing importOptional, Listfrom collections import deque
classTreeNode:
"""Standard binary tree node."""def__init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
self.val = val
self.left = left
self.right = right
DFS - Inorder (Left, Root, Right)
definorder_recursive(root: Optional[TreeNode]) -> List[int]:
"""
Inorder traversal - gives sorted order for BST.
Time: O(n), Space: O(h) where h = height
Args:
root: Root of binary tree
Returns:
List of values in inorder sequence
"""
result = []
defdfs(node: Optional[TreeNode]) -> None:
ifnot node:
return
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
return result
definorder_iterative(root: Optional[TreeNode]) -> []:
result = []
stack = []
current = root
current stack:
current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
result
List
int
"""
Iterative inorder using explicit stack.
Time: O(n), Space: O(h)
Use when: Recursion depth might exceed limit.
"""
while
or
# Go left as far as possible
while
# Process current node
# Move to right subtree
return
DFS - Preorder (Root, Left, Right)
defpreorder_recursive(root: Optional[TreeNode]) -> List[int]:
"""
Preorder traversal - useful for tree serialization.
Time: O(n), Space: O(h)
"""ifnot root:
return []
return ([root.val] +
preorder_recursive(root.left) +
preorder_recursive(root.right))
defpreorder_iterative(root: Optional[TreeNode]) -> List[int]:
"""
Iterative preorder using stack.
Note: Push right first, then left (LIFO).
"""ifnot root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Right first (so left is processed first)if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
DFS - Postorder (Left, Right, Root)
defpostorder_recursive(root: Optional[TreeNode]) -> List[int]:
"""
Postorder traversal - useful for deletion, expression evaluation.
Time: O(n), Space: O(h)
"""ifnot root:
return []
return (postorder_recursive(root.left) +
postorder_recursive(root.right) +
[root.val])
defpostorder_iterative(root: Optional[TreeNode]) -> List[int]:
"""
Iterative postorder using two stacks or modified preorder.
Trick: Modified preorder (root, right, left) then reverse.
"""ifnot root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Left first (so right is processed first after reverse)if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1] # Reverse to get postorder
BFS - Level Order Traversal
deflevel_order(root: Optional[TreeNode]) -> List[List[int]]:
"""
Level-by-level traversal using queue.
Time: O(n), Space: O(w) where w = max width
Returns:
List of levels, each level is a list of values
"""ifnot root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ inrange(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
defzigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
"""
Level order with alternating direction.
Time: O(n), Space: O(w)
"""ifnot root:
return []
result = []
queue = deque([root])
left_to_right = Truewhile queue:
level_size = len(queue)
level = deque()
for _ inrange(level_size):
node = queue.popleft()
if left_to_right:
level.append(node.val)
else:
level.appendleft(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(list(level))
left_to_right = not left_to_right
return result
BST Validation
defis_valid_bst(root: Optional[TreeNode]) -> bool:
"""
Validate if tree is a valid Binary Search Tree.
Time: O(n), Space: O(h)
Property: All left descendants < node < all right descendants
"""defvalidate(node: Optional[TreeNode],
min_val: float,
max_val: float) -> bool:
ifnot node:
returnTrueifnot (min_val < node.val < max_val):
returnFalsereturn (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
□ Null root handled?
□ Base case returns correct value?
□ Both children processed?
□ Return value accumulated correctly?
□ Stack/queue order correct?
□ Tested with single node and empty tree?
