How to derive the proof of this formula for getting right child for a binary tree given inorder and preorder traversals?

Question

I'm looking at this question on leetcode. Given two arrays, inorder and preorder, you need to construct a binary tree. I get the general solution of the question.

Preorder traversal visits root, left, and right, so the left child would be current preorder node index + 1. From that value, you can then know how many nodes are on the left of the tree using the inorder array. In the answers, the formula used to get the right child is "preStart + inIndex - inStart + 1".

I don't want to memorize the formula so I'm wondering if there is a proof for this? I went through the discussion board there, but I'm still missing a link.

Answer 1

For Python Only

• In Python we can also use pop(0) for solving this problem, even though that's inefficient (it would pass though).

• For inefficiency we can likely use deque() with popleft(), however not on LeetCode, because we don't have control over the tree.

class Solution:
    def buildTree(self, preorder, inorder):
        if inorder:
            index = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[index])
            root.left = self.buildTree(preorder, inorder[:index])
            root.right = self.buildTree(preorder, inorder[index + 1:])
            return root

---

For Java and C++, that'd be a bit different just like you said (don't have the proof) but maybe this post would be just a bit helpful:

public class Solution {
    public static final TreeNode buildTree(
        final int[] preorder,
        final int[] inorder
    ) {
        return traverse(0, 0, inorder.length - 1, preorder, inorder);
    }

    private static final TreeNode traverse(
        final int preStart,
        final int inStart,
        final int atEnd,
        final int[] preorder,
        final int[] inorder
    ) {
        if (preStart > preorder.length - 1 || inStart > atEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);
        int inorderIndex = 0;

        for (int i = inStart; i <= atEnd; i++)
            if (inorder[i] == root.val) {
                inorderIndex = i;
            }

        root.left = traverse(preStart + 1, inStart, inorderIndex - 1, preorder, inorder);
        root.right = traverse(preStart + inorderIndex - inStart + 1, inorderIndex + 1, atEnd, preorder, inorder);
        return root;
    }

}

C++

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <unordered_map>

using ValueType = int;

static const struct Solution {
        TreeNode* buildTree(
            std::vector<ValueType>& preorder,
            std::vector<ValueType>& inorder
        ) {
            std::unordered_map<ValueType, ValueType> inorder_indices;

            for (ValueType index = 0; index < std::size(inorder); ++index) {
                inorder_indices[inorder[index]] = index;
            }

            return build(preorder, inorder, inorder_indices, 0, 0, std::size(inorder) - 1);
        }

    private:
        TreeNode* build(
            std::vector<ValueType>& preorder,
            std::vector<ValueType>& inorder,
            std::unordered_map<ValueType, ValueType>& inorder_indices,
            ValueType pre_start,
            ValueType in_start,
            ValueType in_end
        ) {
            if (pre_start >= std::size(preorder) || in_start > in_end) {
                return nullptr;
            }

            TreeNode* root = new TreeNode(preorder[pre_start]);
            ValueType pre_index = inorder_indices[preorder[pre_start]];
            root->left = build(preorder, inorder, inorder_indices, pre_start + 1, in_start, pre_index - 1);
            root->right = build(preorder, inorder, inorder_indices, pre_start + 1 + pre_index - in_start, pre_index + 1, in_end);
            return root;
        }
};