Skip to content

Data Structure Example

Construct Binary Tree from Preorder and Inorder Traversal

Let's move on to a more complex, data structure-related task from LeetCode (Construct Binary Tree from Preorder and Inorder Traversal) which is a variation application that aims to build up the deep understanding of the tree traversal.

Problem Statement:

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

To solve this problem, students need to understand

  • The concept of binary tree and its traversal.
  • The unique properties of preorder and inorder traversal.
  • The recursive approach to build the tree.
 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
# Reference Solution from Instructor
public TreeNode buildTree(int[] preorder, int[] inorder) {
   return buildTree(preorder, inorder, 0, inorder.length-1);
}
public int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder, int start, int end){
    if(start>end)
        return null;

    int rootVal = preorder[index++];
    int leftIndex = search(inorder, start, end, rootVal);
    TreeNode t = new TreeNode(rootVal);
    t.left = buildTree(preorder, inorder, start, leftIndex-1);
    t.right = buildTree(preorder, inorder, leftIndex+1, end);
    return t;
}

public int search(int arr[], int strt, int end, int value){
    int i;
    for (i = strt; i <= end; i++) {
        if (arr[i] == value)
            return 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
# Example Student Submission (Incorrect)
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length <= 0 || inorder.length <= 0) {
        return null;
    }
    if (preorder.length != inorder.length) {
        return null;
    }

    return build(preorder, inorder, 0, inorder.length - 1);
}

public int index = 0;
private TreeNode build(int[] preorder, int[] inorder, int low, int high) {
    if (high < low) {
        return null;
    }

    TreeNode root = new TreeNode(preorder[index]);

    if (high == low) {
        return root;
    }

    int mid = -1;
    for (int i = low; i <= high; i++) {
        if (inorder[i] == preorder[index]) {
            mid = i;
            break;
        }
    }
    index++;
    TreeNode left = build(preorder, inorder, low, mid - 1);
    TreeNode right = build(preorder, inorder, mid + 1, high);
    root.left = left;
    root.right = right;

    return root;
}

Despite the student submission looking correct at first glance, it has an issue with the build helper function. The student's implementation has a bug in the second case condition if (high == low). This condition checker leads to an incorrect tree construction, where the code skips the recursion for the root node and directly builds the left and right subtree. The mistake is subtle, but it reflects an inadequate understanding of the recursive termination condition. Interestingly, this mistake is difficult to directly detect by ChatGPT, possibly because the code logic is mostly correct. However, our repair engine can identify this issue and provide the correct patch to fix the problem.

Fixing Patches from ITS Repair Engine:

  • add if (high == low) { return root; } in build function.

Final ITS Feedback:

  1. Mistake on Termination Condition: This submission prematurely skips the recursive calls and returns the root node before the subtrees are properly constructed. By returning prematurely, the build function does not explore the entire preorder or inorder arrays, leading to an incomplete tree construction.