Skip to content

pydsa.bst

insert 

insert(root: Optional[TreeNode], val: int) -> TreeNode

Insert a value into the BST and return the root.

Source code in pydsa/bst.py 
 9
10
11
12
13
14
15
16
17
18
def insert(root: Optional[TreeNode], val: int) -> TreeNode:
    """Insert a value into the BST and return the root."""
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    # If val == root.val, ignore (no duplicates in this BST)
    return root

generate_random_bst 

generate_random_bst(
    n: int, seed: Optional[int] = None
) -> Optional[TreeNode]

Generate a random BST with values 1..n inserted in random order.

Source code in pydsa/bst.py 
21
22
23
24
25
26
27
28
29
30
31
32
def generate_random_bst(n: int, seed: Optional[int] = None) -> Optional[TreeNode]:
    """Generate a random BST with values 1..n inserted in random order."""
    if n <= 0:
        return None
    if seed:
        random.seed(seed)
    values = list(range(1, n + 1))
    random.shuffle(values)
    root = None
    for val in values:
        root = insert(root, val)
    return root

tree_to_list 

tree_to_list(
    root: Optional[TreeNode],
) -> List[Optional[int]]

Convert BST to list using level-order traversal.

Source code in pydsa/bst.py 
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def tree_to_list(root: Optional[TreeNode]) -> List[Optional[int]]:
    """Convert BST to list using level-order traversal."""
    if not root:
        return []
    result: List[Optional[int]] = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node is not None:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    # Trim trailing Nones
    while result and result[-1] is None:
        result.pop()
    return result

is_valid_bst 

is_valid_bst(root: Optional[TreeNode]) -> bool

Check if the tree is a valid BST using inorder traversal.

Source code in pydsa/bst.py 
55
56
57
58
59
60
61
62
63
64
def is_valid_bst(root: Optional[TreeNode]) -> bool:
    """Check if the tree is a valid BST using inorder traversal."""

    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)

    vals = inorder(root)
    return all(vals[i] < vals[i + 1] for i in range(len(vals) - 1))