There are several variants of tree data structures in computer science. Here are some of them:
Binary Tree
Each node has up to two children, often referred to as the left child and the right child.
- Problem: Symmetric Tree
- Problem: Invert Binary Tree
Binary Search Tree (BST)
It is a binary tree with the property that the key in each node is greater than all keys in its left subtree and less than all keys in its right subtree.
- Problem: Validate Binary Search Tree
- Problem: Convert Sorted Array to Binary Search Tree
AVL Tree
It is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one.
- Problem: Balance a Binary Search Tree
Red-Black Tree
It is a kind of self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black.
B-Tree
It is an extended version of a self-balancing binary search tree that allows for efficient insertion, deletion, and search operations. Each node in a B-Tree contains multiple keys and links to other nodes.
Trie (Prefix Tree)
A tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.
- Problem: Implement Trie (Prefix Tree)
- Problem: Word Search II
Suffix Tree
It is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values.
Segment Tree
A tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point.
- Problem: Range Sum Query — Mutable
Fenwick Tree (Binary Indexed Tree)
A tree data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
- Problem: Range Sum Query 2D — Mutable
Heap
A specialized tree-based data structure that satisfies the heap property. This could be a max-heap (parent node is greater than or equal to its children) or a min-heap (parent node is less than or equal to its children).
- Problem: Kth Largest Element in an Array
- Problem: Merge K Sorted Lists
N-ary Tree (or General Tree)
Each node can have zero or more children, and there is no restrictions like in a binary tree.
- Problem: N-ary Tree Postorder Traversal
- Problem: N-ary Tree Level Order Traversal
Cartesian Tree
A tree data structure that can be used to visualize a sequence of numbers, graphically forming a sequence of “mountains”.
