Binary Trees

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
    • David Eck on Binary Trees
• 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.