Has binary tree properties:
- Collection of nodes
- Each node has at most two children, left and right
Along with the following added properties:
- Ordered, the left subtree contains only nodes with keys less than the node’s key.
- The right subtree contains only nodes with keys greater than the node’s key.
- Duplicates may or may not be allowed. See dealing with duplicates in a binary search tree.
- In-Order Traversal – left, current, right
- Pre-Order Traversal – current, left, right
- Post-Order Traversal – left, right, current
- A balanced tree refers to how evenly the nodes are distributed.
- Having a balanced tree ensures optimal performance (O(log n)) Search , Insert and Delete
- Common types of balanced trees:
- Red-Black Trees
- AVL Trees
Types of completeness:
- Complete Binary Tree – binary tree in which every level is fully filled, except perhaps the last level. To the extent that the last level is filled, it is filled left to right.
- Full Binary Tree – every node has either zero or two children. That is, no nodes have only one child
- Perfect Binary Tree – A perfect binary tree is both full and complete. All leaf nodes will be the same level and this level has the maximum number of nodes. Must ave exactly (2^k) – 1 nodes where k is the number of levels.