Tree Algorithms

Trees

• Definition: In graph theory, a tree is an undirected graph with exactly one path between every pair of nodes.
• Data Structure Implementation: A tree data structure implements a directed acyclic graph where the single source is the root, and the sinks are the leaves.
• Recursive Definition: A tree is a node containing a payload and a list of trees.

Types of Trees

• Arity of trees:
  • Unary tree: linked list
  • Binary trees: each node has at most two children
  • Ternary trees: each node has at most three children
  • N-ary trees: each node has at most n children
  • General trees: each node has arbitrarily many children
• Full trees:
  • In full n-ary trees, each node has exactly n or 0 children

Tree Traversal

• Depth-first search (DFS):
  • Pre-order traversal: perform action before all children
  • In-order traversal: perform action between children
  • Post-order traversal: perform action after children
• Breadth-first search (BFS):
  • Traverse the tree by level
  • Perform action on all nodes on a level before starting next level

Reminder: Binary Trees

• Recursive data type
  • Recursive definition: a tree is a node with two smaller (sub)trees
• Node in a binary tree (TreeNode)
  • TreeNode consists of payload and references to two TreeNodes

TreeNode Class

• Example of a simple TreeNode class:

  class TreeNode {
      int payload;
      TreeNode left;
      TreeNode right;
  }
  

Integer Tree Example

• Illustrates how to create a binary tree with integer payloads in Java.
• The TreeTest class demonstrates the instantiation and construction of a tree with integer values.
• The TreeNode class includes constructors to initialize nodes with a value, and references to left and right children.

Generic Tree Example

• Demonstrates a generic version of the TreeNode class, allowing it to hold any type of payload.
• The class definition class TreeNode<T> uses generics to define the payload type.

Max Value in a Binary Tree

• Base case
  *Maximum of a leaf node is its own payload
• Recursive Call
  *Compute maximum for each child
  *Return maximum of own payload and children

Implementing Tree Algorithms

• As Instance Methods: Within the node class, suitable for recursive algorithms operating locally on an existing tree.
• In Static Methods: Within the node class, useful for recursive or imperative algorithms operating on an external tree.
• In Methods Outside of Node Class: Best for global algorithms that operate on trees arbitrarily, promoting better encapsulation and separation of concerns.

Printing a Tree

• Recursive Algorithm (Preorder):
  1. Print the payload of the current node.
  2. Print the left (smaller) subtree.
  3. Print the right (smaller) subtree.

Inside the Tree

• Direct Access to Fields:
  • The TreeNode class provides direct access to its fields (payload, left, right) for internal operations.

Inside the Tree (Static)

• Direct Access and Safe Null Reference Handling:
  • The static method printPreorder demonstrates how to safely handle null references when traversing the tree.

Outside the Tree

• Encapsulation and Separation of Concerns:
  • The TreeAlgorithms class provides methods to operate on TreeNode objects without direct access to their internal fields.
  • Getter methods (getPayload, getLeft, getRight) are used to access the node's data and children.

Depth-First Search (DFS)

• Pre-order, in-order, and post-order traversals are all types of DFS.

• DFS has a straightforward recursive implementation.

• Pseudocode:

  procedure DFS(Node n):
    performPreorderAction
    for (Node c : n.children):
      DFS(c)
      if (c not last child): performInOrderAction
    performPostOrderAction
  

Iterative DFS

• Requires maintaining a stack.

• In-order and post-order require an additional cursor.

• Java Code:

  public static void iterativePreorder(TreeNode root) {
      Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
      stack.push(root);
      while (!stack.isEmpty()) {
          TreeNode cur = stack.pop();
          System.out.println(cur.getPayload());
          if (cur.getRight() != null)
              stack.push(cur.getRight());
          if (cur.getLeft() != null)
              stack.push(cur.getLeft());
      }
  }
  

Breadth-First Search (BFS)

• BFS traverses the tree level by level.

Iterative BFS

• BFS does not have a natural recursive procedure.

• Iterative implementation requires maintaining a queue.

• Java Code:

  public static void bfs(TreeNode root) {
      Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
      queue.addLast(root);
      while (!queue.isEmpty()) {
          TreeNode cur = queue.removeFirst();
          System.out.println(cur.getPayload());
          if (cur.getLeft() != null)
              queue.addLast(cur.getLeft());
          if (cur.getRight() != null)
              queue.addLast(cur.getRight());
      }
  }