Discussion 8: Reconstructing Binary Trees from Traversals

In lecture, we discussed three different traversal strategies for binary trees: pre-order, in-order and post-order traversals. These traversals provide different ways to “visit” all nodes in a tree and are fundamental for many algorithms, including expression evaluation, tree copying, and serialization. In this discussion, we’ll explore a challenging and interesting problem: Given the pre-order and in-order traversals of a binary tree, reconstruct the original tree.

Learning Outcomes

• Draw node diagrams to visualize tree structures.
• Implement recursive methods to build trees from pre-order and in-order traversal sequences.
• Analyze the correctness and complexity of recursive tree algorithms.
• Reason about the uniqueness of a tree given different types of traversals.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool, meaning it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going so we can make adjustments in future classes. Your grade in discussion is based entirely on attendance and participation; if you show up and you are actively engaged with the activity (working on the activity on your computer, discussing the activity with your group, asking and answering questions, etc.) for the entire 50-minute section period, you will earn full credit. If you complete the activity early, helping other students is a great way to further your own understanding. You do not need to submit any of the work that you complete during discussion.

Since discussion activities are not graded for correctness, we do not place any restrictions on resources that you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from critically thinking to “puzzle” them out.

Working together in small groups is encouraged during discussion!

1
2
3
4
5
6

/**
 * Constructs the subtree described by pre-order traversal segment `preorder[preStart,preEnd)`
 * and in-order traversal segment `inorder[inStart,inEnd)` and returns a reference to its root.
 */
private static ImmutableBinaryTree<Integer> build(int[] preorder, int[] inorder, 
    int preStart, int preEnd, int inStart, int inEnd) { ... } 

1
2
3
4
5
6

/**
 * Constructs the subtree described by pre-order traversal segment `preorder[preStart,preEnd)`
 * and in-order traversal segment `inorder[inStart,inEnd)` and returns a reference to its root.
 */
private static ImmutableBinaryTree<Integer> build(int[] preorder, int[] inorder, 
    int preStart, int preEnd, int inStart, int inEnd) { ... } 

1
2
3
4
5
6

/**
 * Reconstructs a binary tree from its pre-order and in-order traversals.
 * Requires that `preorder` and `inorder` are valid pre-order and in-order 
 * traversals (respectively) of the same non-empty binary tree.
 */
public static ImmutableBinaryTree<Integer> reconstructTree(int[] preorder, int[] inorder) { ... } 

1
2
3
4
5
6

/**
 * Reconstructs a binary tree from its pre-order and in-order traversals.
 * Requires that `preorder` and `inorder` are valid pre-order and in-order 
 * traversals (respectively) of the same non-empty binary tree.
 */
public static ImmutableBinaryTree<Integer> reconstructTree(int[] preorder, int[] inorder) { ... }