Lecture Notes for Computer Algorithms I

25 November 2003 - Binary Trees and Recursion

1. What is a tree?

   1. Null is a tree.

   2. A node pointing to two other trees is a tree.

      1. The two other trees are distinct.

      2. They're the left and right subtrees.

2. The recursive definition of a binary tree is powerful.

   1. Unlike arrays and linked lists, binary trees have non-trivial iterative algorithms.

      1. The notion of next in a binary tree is complex.

   2. Consider searching through unordered values.

      1. Iterative and recursive linear searches through a vector are similar.

         int iterative_search(vector vec, int val)
         
           for i = 0 to v.size - 1
             if vec[i] == val
               return i
           return -1
         
         
         int recursive_search(vector vec, int i, int val)
         
           if i >= vec.size
             return -1
           else if vec[i] == val
             return i
           else return recursive_search(vec, i + 1, val)
         

      2. Iterative and recursive searches through a binary tree are not similar.

         node * recursive_search(node * root, val)
         
           if root == null or root.val == val
             return root
         
           node * found = recursive_search(root->left, val)
           if found == null
             found = recursive_search(root->right, val)
           return found
         
         
         node * iterative_search(node * root, int val)
         
           stack s
           s.push(root)
         
           do root = s.pop()
              if root != null
                if root->val == val
                  return root
                s.push(root->left)
                s.push(root->right)
           while not s.empty()
         
           return null
         

         1. As the search strategy gets more complicated, the difference between the recursive and iterative searches grows.

         2. The recursive search takes advantage of the implicit stack provided by nested procedure calls.

3. Moving between doubly-linked lists and binary trees.

   1. We've already developed the algorithm for turning a list into a tree.

      1. If the list's empty return it as the tree.

      2. Otherwise, walk to the middle node

      3. Turn the sublist to the left into a tree and point to the root.

      4. Turn the sublist to the right into a tree and point to the root.

      5. The trick is, the middle node is pointing to different end of the sublists.

         1. It's pointing to the end of the left sublist, and the beginning of the right sublist.

         node * fold(node * list, unsigned size)
         
           if size > 1
         
             unsigned h = size/2
             list = advance(list, h)
         
             list->next = fold(list->next, size - h - 1)
             list->prev = fold(list, h)
         
           return list
         

   2. It's going in the other direction - from trees to lists - that recursion really shows its stuff.

      1. This is known as flattening the tree to a list.

      2. Flattening a tree to a list is easy if we have access to the ends of the intermediate lists.

         1. If the root's null, then the tree's flattened to a list.

         2. Otherwise,

            1. Flatten the left subtree, and point the root's prev to the end of the resulting list.

            2. Flatten the right subtree, and point the root's next to the beginning of the resulting list.

         (node *, node *) flatten(node * root)
         
           if root = null
             return (root, root)
         
           node * left_b, * right_e
           left_b, root->left = flatten(node->left)
           root->right, right_e = flatten(node->right)
         
           if root->left
             root->left->right = root
           else
             left_b = root
         
           if root->right
             root->right->left = root
           else
             right_e = root
         
           return (left_b, right_e)
         

         See the complete code.

This page last modified on 3 December 2003.