Construct Binary Tree from Inorder and Postorder/Preorder Traversal

From INORDER and POSTORDER

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

Algorithm:

In Postorder, the rightmost element is the root. Search this root in inorder array .Let that index be i ,then left side of i is left subtree and right side of i is right subtree. We use postorder array to create nodes but to construct tree we use inorder array.

Code:

class Solution {
    int index;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index= postorder.length-1;
        return build(postorder,inorder,0,postorder.length-1);
    }
    public TreeNode build(int[] post, int[] in, int start, int end){
        if(start>end){
            return null;
        }
        TreeNode node = new TreeNode(post[index]);
        index--;
        
        int inIndex=search(in,start,end,node.val);
        
        node.right=build(post,in,inIndex+1,end);
        node.left=build(post,in,start,inIndex-1);
        return node;
        
    }
    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;
    }
}

From INORDER and PREORDER

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.

Code:

class Solution {
    int index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,inorder,0,preorder.length-1);
    }
    public TreeNode build(int[] pre, int[] in, int start, int end){
        if(start>end){
            return null;
        }
        TreeNode node = new TreeNode(pre[index]);
        index++;
        if(start==end){
            return node;
        }
        int inIndex=search(in,start,end,node.val);
        node.left=build(pre,in,start,inIndex-1);
        node.right=build(pre,in,inIndex+1,end);
        return node;
        
    }
    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;
    }
}