Trees

CS 106B: Programming Abstractions

Spring 2023, Stanford University Computer Science Department

Lecturer: Chris Gregg, Head CA: Neel Kishnani

---

Slide 2

Announcements

• Assignment 6 due Friday

---

Slide 3

Today's Topics

• Refresh on what pointer diagrams represent
• Quick comment on references to pointers
• Introduction to the tree data structure
  • You've already seen lots of tree structures
  • Tree terminology
  • How do we build trees programatically?
  • Writing code to traverse a tree

---

Slide 4

Pointer Diagram Refresh

• The following diagram was put together by a former CS106B student:
  • Pointers have values that are memory addresses.
  • All variables and objects have their own memory address where they are located
  • The next pointer is a memory address

---

Slide 5

Trees

• We have seen trees in this class before, in the form of decision trees:
• Trees can describe hirearchies:
• Trees can describe websites:
• Trees can desceribe programs (we often call them abstract syntax trees (the following is a figure in an academic paper written by a recent CS 106 student!)

  // Example student solution
  function run() {
    // move then loop
    move();
    // the condition is fixed
    while (notFinished()) {
      if (isPathClear()) {
        move();
      } else {
        turnLeft();
      }
      // redundant
      move();
    }
  }
  

  

---

Slide 6

Trees are inherently recursive

• What is a tree in computer science?
  • A tree is a collection of nodes, which can be empty. If it is not empty, there is a root node, r, and zero or more non-empty subtrees, T1, T2, …, Tk, whose roots are connected by a directed edge from r.

                       (root)
              -----------A--------------
              ↙︎   ↙︎  ↙︎   ↓    ↘︎       ↘︎
             B   C   D   E     F--      G
                    ↙︎   ↙︎ ↘︎   ↙︎ ↘︎ ↘︎      ↘︎
                   H   I   J K   L M       N
                          ↙︎ ↘︎
                         O   P

• There are N nodes and N-1 edges in a tree.
• Tree terminology. In the diagram above:
  • B is a child of A, and F is a child of A and a parent of K, L, M.
  • Nodes with no children are leaves. Nodes B, C, H, I, K, L, M, N, O, and P are all leaves.
  • Nodes with the same parent are siblings. I and J are siblings. K, L, and M are siblings. Nodes O and P are siblings. Nodes H and N do not have any siblings (only children).

---

Slide 7

More Tree Terminology

                       (root)
                         A--------------
                         ↓    ↘︎        ↘︎
                         E     F         G
                        ↙︎ ↘︎   ↙︎ ↘︎ ↘︎       ↘︎
                       I   J K   L M       N
                          ↙︎ ↘︎
                         O   P

• We can define a path from a parent to its children. The path from A to O is: A-E-J-O.
• The path A-E-J-O has a length of three (the number of edges).
• The depth of a node is the length from the root. The depth of node J is 2. The depth of the root is 0.
• The height of a node is the longest path from the node to a leaf. The height of node F is 1. The height of all leaves is 0.
• The height of a tree is the height of the root. The height of the above tree is 3.

---

Slide 8

One Parent, No Cycles

• Tree nodes can only have one parent, and they cannot have cycles
• Not a tree (A has two parents):

  S   N
   ↘︎ ↙︎
    A
  

• Again: not a tree (A has two parents):

    S    N
   ↙︎  ↘︎ ↙︎
  T    A
      ↙︎↘︎ 
     F   O
  

• The following are not trees, either, because you can cycle through the tree. Nodes cannot have children that are on the same level or above on the tree:
• Not a tree (cycle from N back to S):

  →→→→S
  ↑  ↙︎ ↘︎ 
  ↑ T   A
  ↑↙︎
  N
  

• Again: not a tree (the arrow from T to A causes a cycle):

      S
     ↙︎ ↘︎ 
    T→→→A
  ↙︎ 
  N
  

---

Slide 9

Building trees programatically

• To build a tree, we need a new version of our Node. In this case, we want each Node to have a data value (like a linked list), but now we want to pointers, one to the left child, and one to the right child:

  struct TreeNode {
      string data;
      TreeNode* left;
      TreeNode* right; 
  };
  

  

• We don't have to limit ourselves to binary trees, by the way: we could have a ternary tree:

  struct TernaryTreeNode {
      string data;
      TernaryTreeNode* left;
      TernaryTreeNode* middle;
      TernaryTreeNode* right;
  }; 
  

  

• In fact, we could have any number of children (we may look at the Trie data structure, which can be built this way). This is an N-ary Tree:

  struct NAryTreeNode {
      string data;
      Vector<NAryTreeNode*> children;
  }; 
  

  

---

Slide 10

Traversing a Tree

• Often, we will want to do something with each node in a tree. Like linked lists, we can traverse the tree, but it is more involved because of all the branching.
• There are four different ways to traverse a binary tree:
  1. Pre-order
  2. In-order
  3. Post-order
  4. Level-order
• Let's write some code for each traversal to see the differences. We'll look at two trees:

              this
           ↙︎        ↘︎
         is         written
        ↙︎  ↘︎             ↘︎
       a    correctly  sentence
  

• We'll also look at:

             4
           ↙︎  ↘︎
          2     5 
        ↙︎  ↘︎     ↘︎
       1    3      6 
  

• By the way: trees do not have to be complete, like heaps. Any node can have 0, 1, or 2 children.

---

Slide 11

Pre-order traversal

• The algorithm for a pre-order traversal is as follows:
  1. Do something
  2. Go left
  3. Go right
• This is an inherently recursive algorithm
• For our tests, let's make the "Do something" part print the data at a particular node.
• Code:

  void preOrder(TreeNode* tree) {
      if(tree == nullptr) return;
      cout<< tree->data <<" ";
      preOrder(tree->left);
      preOrder(tree->right);
  }
  

---

Slide 12

In-order traversal

• The algorithm for a in-order traversal is as follows:
  1. Go left
  2. Do something
  3. Go right
• This is also an inherently recursive algorithm
• Code:

  void inOrder(TreeNode* tree) {
      if(tree == nullptr) return;
      inOrder(tree->left);
      cout<< tree->data <<" ";
      inOrder(tree->right);
  }
  

---

Slide 13

Post-order traversal

• The algorithm for a post-order traversal is as follows:
  1. Go left
  2. Go right
  3. Do something
• This is also an inherently recursive algorithm
• Code:

  void postOrder(TreeNode* tree) {
      if(tree == nullptr) return;
      postOrder(tree->left);
      postOrder(tree->right);
      cout<< tree->data <<" ";
  }
  

---

Slide 14

Level-order traversal

• A level order traversal is different than all the others – we want to go one level at a time and print out each node, then go to the next level.
• For this tree, it would be:
  • this is written a correctly sentence
• Can we do this recursively!
  • Not easily!
• But, we can use an algorithm you've seen before: breadth first search!
  • This is going to use a queue, just like the BFS you did for your maze solving assignment.
    1. Enqueue the root node
    2. While the queue is not empty
       • dequeue a node
       • do something with the node
       • enqueue the left child if it exists
       • enqueue the right child if it exists
• Code:

  void levelOrder(TreeNode *tree) {
      Queue<TreeNode *>treeQueue;
      treeQueue.enqueue(tree);
      while (!treeQueue.isEmpty()) {
          TreeNode *node = treeQueue.dequeue();
          cout << node->value << " ";
    
         if (node->left != nullptr) {
              treeQueue.enqueue(node->left);
          }
          if (node->right != nullptr) {
              treeQueue.enqueue(node->right);
          }
      }
  }