Back
+20 XP
Concept

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 🌲

# 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>

Checkpoint

In what order does an In-Order traversal visit nodes in a valid Binary Search Tree? 🧠

Practice

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`. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks