Trees

Explore binary trees, AVL trees, and tree traversals

Binary Search Tree

A Binary Search Tree (BST) is a binary tree where each node has at most two children, and the left subtree contains values less than the node, while the right subtree contains values greater than the node.

Time: O(log n) average, O(n) worst for search/insert/delete

Space: O(n)

AVL Tree

A self-balancing binary search tree where the difference between heights of left and right subtrees is at most one. Ensures fast lookups, insertions, and deletions.

Time: O(log n)

Space: O(n)

Red-Black Tree

A self-balancing binary search tree with color properties that ensure the tree remains approximately balanced. Guarantees logarithmic time operations.

Time: O(log n)

Space: O(n)

B-Tree

A balanced tree optimized for systems that read and write large blocks of data. Commonly used in databases and file systems.

Time: O(log n)

Space: O(n)

Trie (Prefix Tree)

A tree data structure used to store strings efficiently by sharing prefixes. Common in autocomplete, dictionaries, and search suggestions.

Time: O(m)

Space: O(n * alphabet_size)