Project 3: Trees and Recursion

(Return to homepage)

In Project 3, you'll write several recursive algorithms to traverse and perform common computations on tree data structures.

Trees are similar to Linked Lists, in that they are composed of several individual nodes carrying values, linked to one another by reference. Unliked Linked Lists, individual tree nodes may have any number (the branching factor) of "next" children nodes, each of which can have children nodes of their own, which can have their own child nodes, and so forth - with the limitation that the tree is acyclic (child nodes may no more than one parent). The tree eventually ends with (several) nodes that have no children, known as leaf nodes.

Due to branching, processing the nodes in the tree structure is more complicated than a simple linear search (plain for loop iteration). Finding a node in the tree requires examining the current node, and then examining the child nodes - and all their children! Our algorithms must both look forwards, down a particular path, and be able to backtrack when necessary.

The solution to this branching problem is recursion. Recursion involves dividing bigger problems into smaller problems, until they become small enough to be trivially solved (the base case). Then, the solutions to the smaller problems are combined to form a solution to the larger problem (the recursive case). Refer to the class notes for examples of Java recursion.

Trees and recursion go hand-in-hand: given the root node of a tree, a child of a tree node is itself a root node of a (sub)tree of the original tree. Recursive tree algorithms treat child nodes as subproblems and combine the recursive calls to compute a solution for the overall tree. In this project, you'll get to implement several recursive (and one iterative) tree algorithms, which are coincidentally quite common as technical interview problems as well.

Let's get to work. Get the Project 3 starter code here! (jUnit dependencies included)

The project code should work out-of-the-box for IntelliJ (running and debugging), but if you're having trouble getting it working, try these IntelliJ setup instructions.

Binary Tree Algorithms

Binary Trees are trees with a branching factor of 2, that is, each node may have up to two children. In this project, we compose binary trees using the BinaryNode<T> class. Each BinaryNode has a payload, and references to BinaryNode children left and right.

The code for all Binary Tree algorithms will be written as static methods contained in trees::BinaryTreeAlgorithms.

Depth-First Binary Tree Traversal

A depth-first search involves examining the deepest child nodes of a tree before examining neighboring child nodes. In real life, this is like walking to the back of a grocery store first, instead of scanning the first item in each aisle. With Binary Trees, there are three ways to perform depth-first search, which you will implement in this project.

• List<T> preOrder(BinaryNode<T>): Perform a pre-order DFS traversal of the tree, returning a list of node payloads in the same order as traversal. A pre-order search returns values in the order of parent node first, then left child (subtree), then right child (subtree).
• List<T> inOrder(BinaryNode<T>): Perform a pre-order DFS traversal of the tree, returning a list of node payloads in the same order as traversal. A pre-order search returns values in the order of the left child (subtree) first, then the parent node, then right child (subtree).
• List<T> postOrder(BinaryNode<T>): Perform a pre-order DFS traversal of the tree, returning a list of node payloads in the same order as traversal. A pre-order search returns values in the order of the left child (subtree) first, then the right child (subtree), and then the parent node.

Hint: All three algorithms are nearly identical and not complicated. The minimal reference solution for each method body is seven lines of code, and has no loops.

Hint: The List interface is implemented by both Java LinkedList and ArrayList. You may use the addAll(...) method to copy and append all the values of another list onto a list.

Binary Search Tree

A Binary Search Tree is a special kind of Binary Tree that enables efficient O(logn)search and lookup. Binary Search Trees have the constraint that all nodes in the left subtree have payloads less than the parent payload, and all nodes in the right subtree have payloads greater than the parent payload.

The diagram above is an example of a Binary Search Tree. Searching a BST is efficient because we always know which child to search to look for the target value: left if the current root value is too high, and right if the current root value is too low. The performance of binary search is O(logn) because with every step, the amount of nodes remaining to search is halved.

• BinaryNode<Integer> binarySearch(BinaryNode<Integer>, Integer): Perform an efficient binary search for the target value. Returns the BinaryNode<Integer> containing the target value once found, or null if the tree does not contain the value. Note that the target value is not necessarily stored in a leaf node, and may appear in the middle of the tree. Your solution should be O(logn) and should not exhaustively search the tree.
  
  
• BinaryNode<Integer> insert(BinaryNode<Integer>, Integer): Inserts a value into a binary search tree, in the correct position. Returns the new BinaryNode<Integer> containing the inserted value, or an existing BinaryNode<Integer> if the tree already contains the value (just like binarySearch. Newly inserted nodes should always be leaf nodes. Your solution should be O(logn) and should not exhaustively search the tree.

Other Recursive Binary Tree Algorithms

• boolean equals(BinaryNode<Integer> A, BinaryNode<Integer> B): Determines if two binary trees are equal, by value. The two trees must have the same node structure and payloads.


• LinkedList<BinaryNode.Direction> path(BinaryNode<T> root, T value): Finds a path from the tree root to a target element. This method returns a Linked List of BinaryNode.Direction enums, which are constant named values similar to static properties on a class. You can refer to left and right using BinaryNode.Direction.left and BinaryNode.Direction.right, respectively.
  
  Note the binary tree you are searching is not necessarily a binary search tree. This algorithm requires an exhaustive (DFS) search.

Hint: The path(...) method is harder than the previous algorithms to implement. Consider trying the other algorithms below first to get more practice with recursion.

Tree Algorithms

Tree algorithms are slightly more complex than binary tree algorithms, as they must account for an arbitrary number of children (compared to up to two children for binary trees). The TreeNode<T> class is the internal node that makes up trees in this project; child nodes are stored in an ArrayList property named children.

Fortunately, the algorithms themselves follow the same recurisve pattern. The only difference now is that you'll need to iterate over all children for the recursive case (use the for-each loop!) and combine their results. Once you figure out one of them, you pretty much have all of them.

• Integer max(TreeNode<Integer> root): Find the maximum value in the tree.
• Integer max(TreeNode<Integer> root): Find the minimum value in the tree.
• LinkedList<TreeNode<Integer>> leaves(TreeNode<Integer> root): Finds and returns a LinkedList containing all the leaf nodes in the tree. Recall that a leaf node is a tree node without children.
• int count(TreeNode<Integer> root): Counts the number of nodes in the tree.
• int depth(TreeNode<T> root): Determines the maximum depth of the tree.
• boolean equals(TreeNode<T> A, TreeNode<T> B): Determines if two trees are equal, by value. The two trees must have the same node structure and payloads.
• LinkedList<Integer> bfs(TreeNode<Integer> root): Performs a breadth-first search on the tree, returning a list of payloads in the same order as searched, from left to right.
  
  Unlike DFS, Breadth-First Search involves examining all children first before moving deeper into the tree. BFS can be implemented iteratively using a queue to store and retrieve nodes (instead of depending on the Stack during recursion). As child nodes are encountered, they should be added to the queue. Then, nodes are processed in the order that the queue provides them.
  
  The Java Queue class can be used for this purpose (official documentation); you can write a loop that continuously iterates over the queue like so: while (!queue.isEmpty()) { ... }. It is safe to add to the queue while iterating.
  
  
• LinkedList<TreeNode<T>> path(TreeNode<T> root, T value) : Finds a path from the tree root to the target element. Note that the return value of this method is different from the path(...) method in the Binary Tree algorithms. This method returns a Linked List of tree nodes describing the path from the root to the target node, inclusive of the target node. An empty list should be returned if the value is not present in the tree.

Running Your Code + Bonus Points

As with the previous projects, this project contains a full test suite (see the test package) that will evaluate your code.

This project contains 15 test cases, one for each method. You only need to pass 14 of the test cases to get a score of 100. If you can pass all 15, you will get 10 bonus points for a total score of 110.

A run script for the entire project test suite is included as run.bat (Windows) or run.sh (Mac/Linux). This will compile your entire project and produce a run report with your estimated grade, including bonus points. Your entire project must compile for the script to work, and your entire project must compile to receive a grade after submission.

You are welcome to modify the tests for debugging purposes, though keep in mind your project will be graded using an unmodified copy of the test suite.

Submission Instructions

See the submissions page for details. Have questions or need help? Post on Piazza!

Critical Analysis Questions

These questions aren't graded, but are similar to those you may see on an exam. You are welcome to discuss these with classmates offline on on Piazza.

• Given n nodes in a tree, what is the Big O of exhaustive tree search? How about the Big O of memory consumed?
• How many nodes are in a tree with branching factor b and maximum depth d?
• How much more efficient is binary search compared to exhaustive search for a tree with 2^30 ≈ 1,000,000 nodes?
• Why is binary search so efficient? What tree structure can cause binary search to be inefficient?
• What memory limitations can DFS run into for an extremely large tree? How about BFS?
• What types could Binary Search Trees be used to store that aren't numbers? What Java interface is common among these types?
• How might you implement a recursive algorithm without using recursion?

(Return to homepage)