Binary trees are a very fundamental data structure in computer science. As you continue to learn and explore in different sub-domains of CS, you’ll see them pop up quite frequently. Here are some things you should Binary Trees and their cousins.

- General Binary Trees
- Pre -, In -, and Post-order traversals
- The height (or depth) of a tree
- Different node terminology (leaf, level, ancestor, descendant, etc.)
- Some info to peruse

- Binary Search Trees
- Remember, binary search trees are binary trees that also conform to the binary search property: all values in the left subtree of a node are smaller and all values in the right subtree of a node are larger (duplicates not withstanding)
- Some algorithms you should think about w.r.t. bin search trees:
- inserting a new value
- searching for a value
- deleting a value from the tree
- determining the height of the tree
- determining if a binary tree is indeed a binary search tree
- what’s the most efficient way to create a copy of a binary search tree?
- what’s the best way to destroy (delete all nodes) a binary search tree?

- Some info to peruse
- David Eck link above
- Cliff Shaffer’s Data Structures and Algorithms book linked above Section 5.4 starting on page 168.

- AVL Tree – a Self Balancing Binary Search Tree
- AVL Balance Property: for every node n in an AVL tree, the height of the left subtree and the height of the right subtree may differ by no more than 1.
- Some info to peruse
- Cliff Shaffer’s PDF Book Section 13.2.1
- AVL Trees at Tutorials Point
- AVL Tree Animation – let’s you see the operation of inserting, searching, and deleting in real time.

## Speak Your Mind