Special Case: Binary Trees

1. If we fix the number of children a node can have at two, then we get what is known as a binary tree.
2. the binary tree has two additional methods: left(v) and right(v) which return the left child or the right child.
3. A proper binary tree is one where all internal nades have exactly two children.
4. A complete binary tree is a proper binary tree where all leaves have the same depth.
5. Properties of a binary tree:
   1. in a complete binary tree, the number of nodes at depth d is 2^d. Proof:
      there are 2⁰ nodes at depth 0.
      if there are 2^d nodes at depth d, then there are 2^d+1 nodes at depth d+1. Each node at depth d has 2 children, so there are 2*2^d nodes at d+1, and 2*2^d= 2^d+1.
   2. in a complete binary tree the height of the tree is log(n+1). Proof:
      The number of nodes in the tree is the sum of the number of nodes at each level:
      n = 2^h+2^h-1+2^h-2+...+2¹+2⁰ = 2^h+1 - 1
      n = 2^h+1 - 1
      n+1 = 2^h+1
      log(n+1) = log(2^h+1)
      log(n+1) = h+1
      h = log(n+1) - 1.
   3. There are some other properties in your book. You should read them.
6. Traversals of binary trees.
   1. We can do the usual traversals: preorder or postorder.
   2. we can also do the insanely fun in-order traversal.

         inorder(v)
          if (hasLeft(v))
            inorder(left(v))
          visit(v)
          if (hasRight(v))
            inorder(right(v))
        

7. We can use inorder traversal to print a binary tree on its side.
   1. If we look at the following tree:
      

      
      The inorder traversal is: H D L I M B E A J F K C G

   2. If we list the nodes from left to right as they appear, we get: H D L I M B E A J F K C G. Coincidence or nefarious plot?
   3. Either way, we can use this to print out a tree:

        binaryTreePrint()
          h = height(root())
          bTreePrint(root(),h)
      
        bTreePrint(v,h)
          if (hasLeft(v))
            bTreePrint(left(v),h)
          for (i = 0; i < (h - depth(v)); i++) print("   ")
          printline(v)
          if (hasRight(v))
            bTreePrint(right(v),h)
        

      This prints out the tree, sideways:

          H
            D
        L
          I
        M
              B
            E
                A
          J
            F
          K
              C
            G
        

8. Lets talk about binary tree implementation.
   1. We could implements it just like a linked list or a general tree, with pointers:

        class BinaryTreeNode {
          Object data;
          BinaryTreeNode leftChild;
          BinaryTreeNode righChild;
        }
        

   2. And that's fine. You've done the general tree, so this should be easy, but there's another way to represent a binary tree that uses no pointers! It takes more space, but is sometimes more convenient.
   3. To understand the basic idea, lets look at the following tree:
      

      

   4. Look at the numbers of the nodes. What is the relationship between the number at a node and the number at its children? Right, the left child is 2n and the right is 2n+1.
   5. So what we'll do is store this tree in an array where each node is located at the index of the array according to its number. Draw picture.
   6. Now a "node" is just represented as an index number, and the element is the item in the array. How do we find the left child of some node x? 2x. and the right child? 2x+1.
   7. How do we find the parent of node x? floor(x/2).
   8. What happens if the tree is not complete? The array has empty parts.
   9. Let's look at the run time of basic binary tree operations in the array vs. linked tree:

      Operation	Array	Linked
      size, isEmpty	O(1)	O(1)
      elements,positions	O(n)	O(n)
      replace	O(1)	O(1)
      root, parent, children, left, right	O(1)	O(1)
      hasLeft/Right, isInternal, isRoot	O(1)	O(1)
      insert	O(n)	O(1)