Summary - BST

Insert items into a BST and print them in-order in a mini task.

Summary - BST

BST: left smaller, node, right larger. Search, insert, delete are O(log n) on a balanced BST; O(n) when unbalanced.

Inorder traversal gives increasing order. Duplicates are usually rejected. AVL or red-black trees provide automatic balance.

The BST is a fundamental data structure for fast search, insert and delete on sorted data.

Exercise Summary: BST inorder

Write inorder(node). Left-root-right; collect values into a list. Print [2, 4, 6] with root = Node(4); root.left = Node(2); root.right = Node(6); print(inorder(root)).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def inorder(node):
    # Left-root-right, return list
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)
root = Node(4)
root.left = Node(2)
root.right = Node(6)
print(inorder(root))

Test yourself

Summary - BST: match the terms

Search

O(log n)
Unbalanced

O(n)
Inorder

Increasing
Duplicate

Reject

Inorder result

BST inorder traversal = ____ order

Show answer

BST inorder traversal = artan order

What is the BST's biggest advantage?
- Fast search+insert+delete
- Simple code
- Stable sort
- Less memory
Show answer

Fast search+insert+delete — Fast search+insert+delete

Next lesson: Balanced tree

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies