Binary Tree Construction

Preorder, Inorder, Postorder

Traversal is a fundamental concept in binary tree, with different orders like Preorder, Inorder, Postorder, and Level Order. But how can we reconstruct a binary tree when given various traversal sequences?

Preorder and Inorder

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int[] preIndex = new int[1];
        Map<Integer, Integer> inorderIndexs = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexs.put(inorder[i], i);
        }
        TreeNode root = buildTree(preIndex, preorder, 0, inorder.length - 1, inorderIndexs);
        return root;
    }

    private TreeNode buildTree(int[] preIndex, int[] preorder, int left, int right,
            Map<Integer, Integer> inorderIndexs) {
        if (left > right) {
            return null;
        }
        int val = preorder[preIndex[0]];
        TreeNode root = new TreeNode(val);
        int inorderIdx = inorderIndexs.get(val);
        preIndex[0]++;
        root.left = buildTree(preIndex, preorder, left, inorderIdx - 1, inorderIndexs);
        root.right = buildTree(preIndex, preorder, inorderIdx + 1, right, inorderIndexs);
        return root;
    }

}

Compute Right PreIndex

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderIndexs = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexs.put(inorder[i], i);
        }
        TreeNode root = buildTree(0, preorder, 0, inorder.length - 1, inorderIndexs);
        return root;
    }

    private TreeNode buildTree(int preIndex, int[] preorder, int left, int right,
            Map<Integer, Integer> inorderIndexs) {
        if (left > right) {
            return null;
        }

        int val = preorder[preIndex];
        TreeNode root = new TreeNode(val);
        int inorderIdx = inorderIndexs.get(val);

        root.left = buildTree(preIndex + 1, preorder, left, inorderIdx - 1, inorderIndexs);
        root.right = buildTree(preIndex + 1 + inorderIdx - left, preorder, inorderIdx + 1, right, inorderIndexs);
        return root;
    }

}

Get 8techlife’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Postorder and Inorder

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> inorderIndexs = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexs.put(inorder[i], i);
        }
        int[] postIndex = new int[] { postorder.length - 1 };
        TreeNode root = buildTree(postIndex, postorder, 0, postorder.length - 1, inorderIndexs);
        return root;
    }

    private TreeNode buildTree(int[] postIndex, int[] postorder, int left, int right,
            Map<Integer, Integer> inorderIndexs) {
        if (left > right) {
            return null;
        }
        int val = postorder[postIndex[0]];
        TreeNode root = new TreeNode(val);
        int inorderIndex = inorderIndexs.get(val);
        postIndex[0]--;
        root.right = buildTree(postIndex, postorder, inorderIndex + 1, right, inorderIndexs);
        root.left = buildTree(postIndex, postorder, left, inorderIndex - 1, inorderIndexs);
        return root;
    }
}

Compute right PostIndex

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> inorderIndexs = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexs.put(inorder[i], i);
        }
        TreeNode root = buildTree(postorder.length - 1, postorder, 0, postorder.length - 1, inorderIndexs);
        return root;
    }

    private TreeNode buildTree(int postIndex, int[] postorder, int left, int right,
            Map<Integer, Integer> inorderIndexs) {
        if (left > right) {
            return null;
        }
        int val = postorder[postIndex];
        TreeNode root = new TreeNode(val);
        int inorderIndex = inorderIndexs.get(val);

        root.right = buildTree(postIndex - 1, postorder, inorderIndex + 1, right, inorderIndexs);
        root.left = buildTree(postIndex - 1 - (right - inorderIndex), postorder, left, inorderIndex - 1, inorderIndexs);
        return root;
    }
}

Preorder and Postorder

class Solution {    
    public TreeNode buildTree(int[] preorder, int[] postorder) {
        Map<Integer, Integer> postorderIndexs = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            postorderIndexs.put(postorder[i], i);
        }
        int[] preIndex = new int[1];
        TreeNode root = buildTree(preIndex, preorder, 0, preorder.length - 1, postorderIndexs);
        return root;
    }

    private TreeNode buildTree(int[] preIndex, int[] preorder, int left, int right,
            Map<Integer, Integer> postorderIndexs) {
        if (left > right) {
            return null;
        }
        int val = preorder[preIndex[0]];
        TreeNode root = new TreeNode(val);
        preIndex[0]++;
        // is current node a leaf ?
        if (left == right || preIndex[0] >= preorder.length) {
            return root;
        }
        int leftSubTreeRoot = preorder[preIndex[0]];
        int leftIndex = postorderIndexs.get(leftSubTreeRoot);
        root.left = buildTree(preIndex, preorder, left, leftIndex, postorderIndexs);
        root.right = buildTree(preIndex, preorder, leftIndex + 1, right - 1, postorderIndexs);
        return root;
    }
}

The implementation of this case may be incorrect because postorder sequences do not provide explicit boundaries between left and right children.

As you can see, node 3 is not the left subtree root, instead it is the right subtree root. If the tree is a complete binary tree, then it works.