Construct Binary Tree from Preorder and Inorder Traversal Editorial

Practice Problem Link: Construct Binary Tree from Preorder and Inorder Traversal

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

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

Naive Approach

The problem can be solved recursively based on the fact that in preorder traversal the root is visited first followed by its nodes.

• Pick an element from the preorder traversal and create a new node using that element say currNode.
• Search the index of that element in the inorder traversal. Let the index be currInorderIndex.
• All the elements before the currInorderIndex must be part of the left subtree of the currNode and all the elements after it must be part of the right subtree of the currNode.
• Recursively repeat the above steps for the elements before the currInorderIndex and make them the left subtree of the currNode.
• Recursively repeat the above steps for the elements after the currInorderIndex and make them the right subtree of the currNode.
• Return currNode.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
Node* constructTreeUtil(vector<int> &preorder, int &preorderIndex, vector<int> &inorder, int inorderStart, int inorderEnd) {
	if (inorderStart > inorderEnd) {
		return NULL;
	}
	Node* currNode = new Node(preorder[preorderIndex]);
	preorderIndex++;
	if (inorderStart == inorderEnd) {
		return currNode;
	}
	int currInorderIndex = - 1;
	for (int i = inorderStart; i <= inorderEnd; i++) {
		if(inorder[i] == currNode->data) {
			currInorderIndex = i;
			break;
		}
	}
	currNode->left = constructTreeUtil(preorder, preorderIndex, inorder, inorderStart, currInorderIndex - 1);
	currNode->right = constructTreeUtil(preorder, preorderIndex, inorder, currInorderIndex + 1, inorderEnd);
	return currNode;
}
Node* constructTree(vector<int> &preorder, vector<int> &inorder) {
	int preorderIndex = 0;
    return constructTreeUtil(preorder, preorderIndex, inorder, 0, inorder.size() - 1);
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	static int preorderIndex;
	Node constructTreeUtil(int[] preorder, int[] inorder, int inorderStart, int inorderEnd) {
		if (inorderStart > inorderEnd) {
			return null;
		}
		Node currNode = new Node(preorder[preorderIndex]);
		preorderIndex++;
		if (inorderStart == inorderEnd) {
			return currNode;
		}
		int currInorderIndex = - 1;
		for (int i = inorderStart; i <= inorderEnd; i++) {
			if(inorder[i] == currNode.data) {
				currInorderIndex = i;
				break;
			}
		}
		currNode.left = constructTreeUtil(preorder, inorder, inorderStart, currInorderIndex - 1);
		currNode.right = constructTreeUtil(preorder, inorder, currInorderIndex + 1, inorderEnd);
		return currNode;
	}
	Node constructTree(int[] preorder, int[] inorder) {
		preorderIndex = 0;
		return constructTreeUtil(preorder, inorder, 0, inorder.length - 1);
	}
}

Optimal Approach

The naive approach can be optimized by storing the indexes of inorder traversal in a hashmap. By doing this, searching can be done in O(1) time.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
unordered_map<int, int> inorderIndex;
Node* constructTreeUtil(vector<int> &preorder, int &preorderIndex, vector<int> &inorder, int inorderStart, int inorderEnd) {
	if (inorderStart > inorderEnd) {
		return NULL;
	}
	Node* currNode = new Node(preorder[preorderIndex]);
	preorderIndex++;
	if (inorderStart == inorderEnd) {
		return currNode;
	}
	int currInorderIndex = inorderIndex[currNode->data];
	currNode->left = constructTreeUtil(preorder, preorderIndex, inorder, inorderStart, currInorderIndex - 1);
	currNode->right = constructTreeUtil(preorder, preorderIndex, inorder, currInorderIndex + 1, inorderEnd);
	return currNode;
}
Node* constructTree(vector<int> &preorder, vector<int> &inorder) {
	inorderIndex.clear();
	for (int i = 0; i < inorder.size(); i++) {
		inorderIndex[inorder[i]] = i;
	}
	int preorderIndex = 0;
    return constructTreeUtil(preorder, preorderIndex, inorder, 0, inorder.size() - 1);
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	HashMap<Integer, Integer> inorderIndex = new HashMap<Integer, Integer>();
	static int preorderIndex;
	Node constructTreeUtil(int[] preorder, int[] inorder, int inorderStart, int inorderEnd) {
		if (inorderStart > inorderEnd) {
			return null;
		}
		Node currNode = new Node(preorder[preorderIndex]);
		preorderIndex++;
		if (inorderStart == inorderEnd) {
			return currNode;
		}
		int currInorderIndex = inorderIndex.get(currNode.data);
		currNode.left = constructTreeUtil(preorder, inorder, inorderStart, currInorderIndex - 1);
		currNode.right = constructTreeUtil(preorder, inorder, currInorderIndex + 1, inorderEnd);
		return currNode;
	}
	Node constructTree(int[] preorder, int[] inorder) {
		inorderIndex.clear();
		for (int i = 0; i < inorder.length; i++) {
			inorderIndex.put(inorder[i], i);
		}
		preorderIndex = 0;
		return constructTreeUtil(preorder, inorder, 0, inorder.length - 1);
	}
}