Discussion 8: Reconstructing Binary Trees from Traversals

Solutions

Download Solution Code download

Exercise 1: Converting Between Tree Structure and Traversals

Suppose we have the following binary tree whose nodes are labeled with Integers.

(a)

Write out the pre-order, in-order and post-order traversals of this tree.

Pre-order: 0, 1, 6, 2, 3, 4, 5

In-order: 6, 1, 2, 0, 4, 5, 3

Post-order: 6, 2, 1, 5, 4, 3, 0

Now, let's imagine doing this process in reverse. Suppose that you were given only the pre-order and in-order traversals of this tree. Let's think about how we can use this information to re-construct the picture of the tree.

(b)

Which traversal can we use to determine the root of the tree? How can we determine this?

We can use the pre-order traversal to determine this, since the root is always the first element of the pre-order traversal.

(c)

Now that you’ve identified the tree’s root, can you determine which nodes belong in its left subtree and which nodes belong in its right subtree? Which traversal will be helpful for determining this?

We can use the in-order traversal to determine this. All of the nodes in the left subtree will appear before the root in the in-order traversal. All of the nodes in the right subtree will appear after the root in the in-order traversal.

(d)

If we perform a pre-order traversal of the nodes in the left subtree, in which order will they be listed? Same question for an in-order traversal.

For both subtree traversals, the nodes in the left subtree will be listed in the same order that they are listed in the full tree traversal. This is because the traversals are defined recursively, where one step is to carry out (i.e., visit consecutively) a traversal of the left subtree.

(e)

Using your answer for part (c), describe a recursive procedure that uses sub-ranges of the pre-order and in-order traversal arrays to reconstruct the left and right subtrees?

For our procedure, we can first use the pre-order traversal to identify the root. Then, we can use the in-order traversal to partition the remaining nodes into the left and right subtrees. From these partitions, we can determine the sub-ranges of the pre-order and in-order traversals that are pre-order and in-order traversals of the left subtree. We can recursively reconstruct the left subtree using these ranges (and similarly recursively reconstruct the right subtree).

(f)

Use the ideas from the previous parts to draw the tree with the following traversals:

Pre-order: 3, 1, 4, 0, 2, 6, 5

In-order: 1, 4, 3, 2, 0, 5, 6

Exercise 2: Planning the build() Method

The build() helper method is the core of our code to reconstruct a binary tree from its pre-order and in-order traversals. Its purpose is simple yet powerful: Given a segment of the pre-order array and the corresponding segment of the in-order array, construct the subtree represented by those segments and return its root node. In essence, build() focuses on one part of the tree at a time — it identifies the current root, splits the arrays into left and right subtrees, and recursively constructs each subtree, ultimately connecting them into the complete binary tree.

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) { ... } 

(a)

Understanding the base cases:

What should the method return if the current pre-order/in-order segments are empty (i.e., there is no subtree left to construct)? What condition will identify this case?

If the current pre-order or in-order segments are empty (meaning there are no elements left to construct), the method should return null because there is no subtree to build. This case can be identified when preEnd - preStart == 0 or inEnd - inStart == 0.

What should the method return if the segment contains exactly one node? What condition will identify this case?

If the segment contains exactly one node, the method should return a new ImmutableBinaryTree containing that single node as the root, with both left and right subtrees set to null. This situation can be identified when preEnd - preStart == 1 or inEnd - inStart == 1.

(b)

Finding the subtree segments:

Now, suppose we are not in one of the base cases.

Write an expression with value equal to the root of the subtree returned by this method.

The root of the current subtree is always the first element in the current pre-order segment, so the expression is: int rootVal = preorder[preStart];

How can we use the root to determine the sub-ranges of inorder corresponding to its left/right subtrees?

We can find the index of rootVal in the inorder array. All elements to the left of this index in inorder belong to the left subtree. All elements to the right of this index in inorder belong to the right subtree. If rootIndex is the index of rootValue in inorder, then left subtree → inorder[inStart, rootIndex), right subtree → inorder[rootIndex + 1, inEnd).

How can we determine the sub-ranges of preorder corresponding to its left/right subtrees?

The size of the left subtree is leftSize = rootIndex - inStart. Using that, we can divide the preorder segment as: left subtree → preorder[preStart + 1, preStart + leftSize + 1), right subtree → preorder[preStart + leftSize + 1, preEnd)

(c)

Dividing the segments for recursion:

After determining the correct sub-ranges for the left and right subtrees in both arrays, how can you recursively call build() to construct each subtree?

We call build() again on the left and right sub-ranges. The call for the left subtree uses the indices of the left segment in both arrays, and the call for the right subtree uses the right segment. For example:

left = build(preorder, inorder, preStart + 1, preStart + leftSize + 1, inStart, rootIndex)

right = build(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd)

How do we use the return values of these recursive calls to build the final tree that we must return?

Each recursive call returns a subtree. We combine them by creating a new tree node whose root value is rootVal, with the left child being the subtree returned from the left call and the right child being the subtree returned from the right call.

Exercise 3: The TreeReconstruction class

(a)

Use your ideas from the previous exercise to complete the definition of the build() method.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


/**
 * 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) {

  assert preEnd - preStart == inEnd - inStart; // sanity check: both ranges should have same length
  if (preEnd - preStart == 0) { // empty range
    return null;
  } else if (preEnd - preStart == 1) { // one-element range
    assert preorder[preStart] == inorder[inStart]; // sanity check: same value
    return new ImmutableBinaryTree<>(preorder[preStart], null, null);
  }

  // Step 1: Use pre-order traversal to identify subtree root
  int rootVal = preorder[preStart];

  // Step 2: Use in-order traversal to determine left subtree size
  int rootIndex = indexOf(inorder, rootVal, inStart);
  int leftSize = rootIndex - inStart;<code>

  // Step 3: Recursively construct left subtree
  ImmutableBinaryTree<Integer> left = build(preorder, inorder, preStart + 1, 
    preStart + 1 + leftSize, inStart, rootIndex);

  // Step 4: Recursively construct right subtree
  ImmutableBinaryTree<Integer> right = build(preorder, inorder,
    preStart + 1 + leftSize, preEnd, rootIndex + 1, inEnd);

  // Step 5: Construct subtree to return
  return new ImmutableBinaryTree<>(rootVal, left, right);
} 

/**
 * Returns the index `i` such that `a[i] == key`. Requires that `key` is present 
 * in `a` at an index `>= start`.
 */
private static int indexOf(int[] a, int key, int start) {
  int i = start;
  while(a[i] != key) {
    i++;
  }
  return i;
} 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


/**
 * 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) {

  assert preEnd - preStart == inEnd - inStart; // sanity check: both ranges should have same length
  if (preEnd - preStart == 0) { // empty range
    return null;
  } else if (preEnd - preStart == 1) { // one-element range
    assert preorder[preStart] == inorder[inStart]; // sanity check: same value
    return new ImmutableBinaryTree<>(preorder[preStart], null, null);
  }

  // Step 1: Use pre-order traversal to identify subtree root
  int rootVal = preorder[preStart];

  // Step 2: Use in-order traversal to determine left subtree size
  int rootIndex = indexOf(inorder, rootVal, inStart);
  int leftSize = rootIndex - inStart;<code>

  // Step 3: Recursively construct left subtree
  ImmutableBinaryTree<Integer> left = build(preorder, inorder, preStart + 1, 
    preStart + 1 + leftSize, inStart, rootIndex);

  // Step 4: Recursively construct right subtree
  ImmutableBinaryTree<Integer> right = build(preorder, inorder,
    preStart + 1 + leftSize, preEnd, rootIndex + 1, inEnd);

  // Step 5: Construct subtree to return
  return new ImmutableBinaryTree<>(rootVal, left, right);
} 

/**
 * Returns the index `i` such that `a[i] == key`. Requires that `key` is present 
 * in `a` at an index `>= start`.
 */
private static int indexOf(int[] a, int key, int start) {
  int i = start;
  while(a[i] != key) {
    i++;
  }
  return i;
} 

(b)

Complete the definition of the reconstructTree() method. This definition should consist of a single call to the build() helper method, with appropriately chosen parameters.

1
2
3
4
5
6
7
8
9


/**
 * 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) { 
  int n = preorder.length;
  return build(preorder, inorder, 0, n, 0, n);
} 

1
2
3
4
5
6
7
8
9


/**
 * 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) { 
  int n = preorder.length;
  return build(preorder, inorder, 0, n, 0, n);
} 

(c)

What are the worst-case time complexity and space complexity of your reconstructTree() method, expressed in terms of \(N=\) preorder.length ?

The worst-case time complexity of reconstructTree() is \(O(N^2)\), where \(N\) = preorder.length. This happens because, for each recursive call, we may need to search for the root value in the inorder array (an \(O(N)\) operation), and there can be up to \(N\) recursive calls in the worst case (for a skewed tree). The worst-case space complexity is \(O(N)\). This comes from the recursion stack depth, which can be as large as \(N\) in the case of a completely skewed tree.

Exercise 4: (Bonus Challenge) Considering Other Traversals

Up to this point, you’ve seen how combining pre-order and in-order traversals allows you to uniquely reconstruct a binary tree. What if we try using the pre-order and post-order traversals instead?

Give an example of two different binary trees that have the same pre-order and post-order traversals. This shows that the in-order traversal is necessary to uniquely reconstruct a binary tree.