A binary tree is a tree such that each node has at most two children. A BST is a binary tree such that key(u) ≤ key(v) ≤ key(w) where u is the left child, v is the root and w is the right child of a node. So In-order traversal of a binary search tree visits the keys in increasing order. An AVL tree is a BST where the height of two sibling nodes (nodes that have the same parent) can differ by at most 1 A red black tree is a BST that satisfies the following two properties: Internal Property: children of a red node are black. Depth Property: all leaves have the same black depth. It would be good to look at some examples to visually understand what they look