class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
# Build a tree:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)# Inorder: Left, Root, Right
def inorder(node):
if node:
inorder(node.left)
print(node.val, end=' ')
inorder(node.right)
# Output: 4 2 5 1 3
# Preorder: Root, Left, Right
def preorder(node):
if node:
print(node.val, end=' ')
preorder(node.left)
preorder(node.right)
# Output: 1 2 4 5 3
# Postorder: Left, Right, Root
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.val, end=' ')
# Output: 4 5 2 3 1
# Level-order (BFS)
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
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
# [[1], [2, 3], [4, 5]]class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
self._insert(self.root, val)
def _insert(self, node, val):
if val < node.val:
if node.left:
self._insert(node.left, val)
else:
node.left = TreeNode(val)
else:
if node.right:
self._insert(node.right, val)
else:
node.right = TreeNode(val)
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if not node or node.val == val:
return node
return self._search(node.left if val < node.val else node.right, val)
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.val)
self._inorder(node.right, result)
bst = BST()
for x in [5, 3, 7, 1, 4, 6, 8]:
bst.insert(x)
print(bst.inorder()) # [1, 3, 4, 5, 6, 7, 8] — sorted!def max_depth(node):
if not node:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def _find(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
t = Trie()
t.insert('hello')
t.insert('hey')
print(t.search('hello')) # True
print(t.search('hell')) # False
print(t.starts_with('he')) # True
print(t.starts_with('hi')) # FalseCreate a `TreeNode` class. Implement `build_tree()` that returns the example tree (1→2,3; 2→4,5). Implement `inorder`, `preorder`, `postorder` (all returning lists), and `level_order` (returning list of lists). Implement `max_depth`. Create a `BST` class with `insert`, `search`, and `inorder`. Create a `Trie` class with `insert`, `search`, and `starts_with`. Demonstrate all with clear output.