105. Construct Binary Tree from Preorder and Inorder Traversal

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input:

preorder = [3, 9, 20, 15, 7]

inorder = [9, 3, 15, 20, 7]

Output: [3, 9, 20, null, null, 15, 7]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private int preorderIndex = 0;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null) return null;
        return buildTree(preorder, inorder, 0, preorder.length-1);
    }
    
    private TreeNode buildTree(int[] pre, int[] in, int start, int end) {
        if(start > end) return null;
        
        TreeNode node = new TreeNode(pre[preorderIndex++]);
        
        if(start == end) return node;
        
        int inorderIndex = findInorderIndex(in, start, end, node.val);
        
        node.left = buildTree(pre, in, start, inorderIndex-1);
        
        node.right = buildTree(pre, in, inorderIndex+1, end);
        
        return node;
    }
    
    private int findInorderIndex(int[] in, int start, int end, int val) {
        while(start <= end) {
            if(in[start] == val) break;
            start++;
        }
        return start;
    }
}

Follow up