Binary Search Trees & In-Order Traversal
A Binary Search Tree (BST) stores smaller keys in the left child and larger keys in the right child. An In-Order traversal (Left -> Node -> Right) visits all keys in sorted order 🌲.
class BSTNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
root = BSTNode(20)
root.left = BSTNode(10)
root.right = BSTNode(30)
# In-Order Traversal:
def inorder(node):
if node:
inorder(node.left)
print(node.val, end=" ")
inorder(node.right)
inorder(root) # 10 20 30 🌲
# 7. Binary Search Trees & In-Order Traversal A Binary Search Tree (BST) stores smaller keys in the left child and larger keys in the right child. An In-Order traversal (Left -> Node -> Right) visits all keys in sorted order 🌲. ```python class BSTNode: def __init__(self, val): self.val = val self.left = None self.right = None root = BSTNode(20) root.left = BSTNode(10) root.right = BSTNode(30) # In-Order Traversal: def inorder(node): if node: inorder(node.left) print(node.val, end=" ") inorder(node.right) inorder(root) # 10 20 30 🌲 ``` In a balanced BST, lookups, insertions, and deletions run in $O(\log n)$ time. In-Order traversal produces perfectly sorted data without calling `sort()`! 🌲 --- ### Question In what order does an In-Order traversal visit nodes in a valid Binary Search Tree? 🧠- [ ] a. Strictly in ascending sorted order 🌲 - [ ] b. Reverse order from maximum to minimum - [ ] c. Level-by-level from top to bottom - [ ] d. In random order --- ### Challenge Construct a BST with root `15`, left child `5`, right child `25`. Write an inorder traversal function appending values to a list `res`. Print `res`. 🎯 <details> <summary>Solution</summary> ```python class BSTNode: def __init__(self, val): self.val = val self.left = None self.right = None root = BSTNode(15) root.left = BSTNode(5) root.right = BSTNode(25) res = [] def inorder(n): if n: inorder(n.left) res.append(n.val) inorder(n.right) inorder(root) print(res) ``` </details>