Category: Trees
Topics: tree traversal, recursion, hierarchical data, expression parsing
A hierarchical data structure where each node has at most two children, referred to as the left child and right child, with no ordering constraint on node values.
| Operation | Average | Worst | Description |
|---|---|---|---|
| Search | O(n) | O(n) | Must traverse entire tree |
| Insert | O(n) | O(n) | Find position, then insert |
| Delete | O(n) | O(n) | Find node, then remove |
| Traversal | O(n) | O(n) | Visit all nodes |
| Height | O(n) | O(n) | Calculate tree height |
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Tree traversals
def preorder(node):
"""Root -> Left -> Right"""
if node:
print(node.val)
preorder(node.left)
preorder(node.right)
def inorder(node):
"""Left -> Root -> Right"""
if node:
inorder(node.left)
print(node.val)
inorder(node.right)
def postorder(node):
"""Left -> Right -> Root"""
if node:
postorder(node.left)
postorder(node.right)
print(node.val)
def level_order(root):
"""BFS - level by level"""
if not root:
return
from collections import deque
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Common operations
def height(node):
if not node:
return -1
return 1 + max(height(node.left), height(node.right))
def count_nodes(node):
if not node:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
O(n) for n nodes. Recursive operations use O(h) stack space where h is tree height. Level-order traversal uses O(w) queue space where w is maximum width.
Pros:
Cons: