\

Construct Binary Tree From Preorder And Inorder Traversal

Difficulty: N/A | Solved: December 20, 2025

Problem

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.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1] Output: [-1]

Brainstorming

Brute force

okay so what is pre order root->left->right inorder left->root-> right

we need to make a tree node by node using these 2 informations

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

on the face of it a crude way to think of it would be to see the array indexes as position like for eg in array preorder the value at preorder[0] will always be the root of the binary tree so we can just do

root = TreeNode(preorder[0]) at each node we would then need to decide what goes to its left and what goes to its right

like in the above case root.left = TreeNode(preorder[1]) root.right = TreeNode(preorder[2])

but it would be very tricky to pick array indexes in insolation and force fit them in the tree especially in a loop we have another array in order maybe we can use that

lets take the above example and try to see if we can come up with a pattern 0 1. 2. 3. 4 preorder = [3, 9, 20, 15, 7] r r.l r.r r.r.l r.r.r

inorder = [9, 3, 15, 20, 7] r.l. r. r.r.l r.r. r.r.r

with array indexes it will be pretty hard to keep a track of maybe some sort of LIFO or FIFO data structure can help that give us a way to peel off this but even then it will be slightly challlenging. A heap is a complete binary tree maybe we can check that. but i am concerned that with its property of complete tree and keeping the minimum and maximum can cause a problem , since we are dealing with a binary tree and not a binary search tree

since we have 2 arrays maybe we can come up with an algorithm that takes the heaps priority queue property along with it?

  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-16 10:42) - (end:: 2025-12-16 11:02)

Optimal Solution

O(N^2) Brute force

This is a brilliant brainstorming session. You’ve correctly identified the most important piece of information, asked the right questions, and even considered (and correctly reasoned about) alternative data structures.

Your Core Insight (The Key to the Entire Problem):

“in array preorder the value at preorder[0] will always be the root of the binary tree”

100% correct. This is the starting point for everything. The first element of any preorder traversal is the root of the tree (or subtree) that traversal represents.

Your Next Insight (Also Correct):

“we have another array in order maybe we can use that”

Yes. Once you know the root’s value (from preorder[0]), the inorder array tells you everything you need to know about the structure.

  • Find the root’s value in the inorder array.
  • Everything to the left of the root’s value in the inorder array belongs to the left subtree.
  • Everything to the right of the root’s value in the inorder array belongs to the right subtree.

Let’s use your example: preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7]

  1. Root: From preorder, the root is 3.
  2. Find Root in inorder: 3 is at index 1 in the inorder array.
  3. Partition inorder:
    • Left subtree elements (from inorder): [9]
    • Right subtree elements (from inorder): [15, 20, 7]

This is the recursive “Aha!” moment.

We now have two smaller, independent subproblems:

  • Subproblem 1 (Left Child): Construct a tree from its inorder traversal [9] and its preorder traversal.
  • Subproblem 2 (Right Child): Construct a tree from its inorder traversal [15, 20, 7] and its preorder traversal.

This immediately tells us that recursion is the natural way to solve this.

The Self-Nudge Questions:

Question 1: Finding the Sub-Array Traversals

We have the inorder arrays for the left and right subtrees. But what are their preorder arrays?

  • The left subtree’s inorder is [9]. It has 1 element.
  • The right subtree’s inorder is [15, 20, 7]. It has 3 elements.

Now look at the original preorder: [3, 9, 20, 15, 7]

  • The root is 3.
  • The next elements in a preorder traversal are always from the left subtree. How many elements are in the left subtree? We just found out: 1 element.
  • So, the preorder traversal for the left subtree must be the next 1 element after the root: [9]
  • The elements after that must be the preorder traversal for the right subtree.
  • So, the preorder traversal for the right subtree must be [20, 15, 7].

Question 2: Structuring the Recursion

So, our recursive function will build a tree for a given preorder and inorder subarray. build(preorder_subarray, inorder_subarray)

Inside this function:

  1. Base Case: If the input arrays are empty, what should you return?
  2. Find the root: Take the first element of the preorder_subarray.
  3. Find the partition point: Find that root’s value in the inorder_subarray.
  4. Create the subproblems: Slice the inorder_subarray and preorder_subarray to get the correct arrays for the left and right children.
  5. Recurse:
    • root.left = build(left_preorder_subarray, left_inorder_subarray)
    • root.right = build(right_preorder_subarray, right_inorder_subarray)
  6. Return the root you created.

This approach is correct, but slicing arrays (array[:]) over and over is inefficient (O(N)).

Question 3 (The Optimisation): Instead of passing copies of subarrays, can we just pass pointers/indices that define the boundaries of the current preorder and inorder subarrays we’re working on? build(preorder, inorder, pre_start, pre_end, in_start, in_end)

(Prompt): Focus on the inefficient slicing version first (Question 2). Try to write the pseudocode for build(preorder_subarray, inorder_subarray). How do you calculate the slices for the recursive calls? (Hint: you need the len of the left inorder subarray).

okay so got it , the heap approach maybe was me going a bit astray i think my original insights combined with recursive approach would work the best here so if i understand correctly the brute force approach would be array slicing to the multitude

the flow is something like this

  1. for every tree we find the root using the preorder traversal at the start the root is at index 0 going ahead it would be somewhere ahead in the array for subtrees
  2. we find the index of this root in the inorder traversal lets call it i. once we find it the elements from 0 till that index i will be the left subtree in_order_left_tree_at_root_i = in_order[:i] anything from i+1 till the end of the array will be right_subtree in_order_right_tree_at_root_i = in_order[i+1:]
  3. We need to do this similar exercise for post order too . This can be done using the length of the in_order_arrays
    1. we have in_order_left_tree_at_root_i we know in preorder the number of elements in this array is equal to the number of elements in pre order after the root that are the left of the root , and post that what we have is the elements to the right of the root pre_order_left_tree_at_root_i = pre_order[1:len(in_order_left_tree_at_root_i+1] and the right of it will be pre_order_right_tree_at_root_i = [len(in_order_left_tree_at_root_i+1:]
  4. to make this brute force work we will cheat to get the index for the root in inorder array using i = inorder_array.index(root)

below is the python code

This is the Brute force solution


class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


pre_order = [3,9,20,15,7]
in_order = [9,3,15,20,7]

def build(pre_order_sub_array, in_order_sub_array):
	# base case 
	if not pre_order_sub_array or not in_order_sub_array
		return None
	root = TreeNode(pre_order_sub_array[0])
	# index of root
	i = in_order_sub_array.index(pre_order_sub_array[0])
	# get the inorder sub array
	in_order_left_tree_at_root_i = in_order_sub_array[:i]
	in_order_right_tree_at_root_i = in_order_sub_array[i+1:]
	# get the pre order sub array
	pre_order_left_tree_at_root_i = pre_order_sub_array[1:len(in_order_left_tree_at_root_i)+1]
	pre_order_right_tree_at_root_i = pre_order_sub_array[len(in_order_left_tree_at_root_i)+1:]
	root.left = build(pre_order_left_tree_at_root_i, in_order_left_tree_at_root_i)
	root.right = build(pre_order_right_tree_at_root_i, in_order_right_tree_at_root_i)
	
	return root


build(pre_order, in_order)

Optimisation

  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-16 11:02) - (end:: 2025-12-16 12:00)

The Inefficiency:
The two main inefficiencies are:

  1. in_order_sub_array.index(…): This is an O(N) scan inside each recursive call.
  2. pre_order_sub_array[:]: Slicing creates copies of the arrays, which takes time and memory.

Instead of passing copies of subarrays, can we just pass pointers/indices that define the boundaries of the current preorder and inorder subarrays we’re working on?

This is the key. Let’s design a helper function that works with indices.

build_helper(pre_start, pre_end, in_start, in_end)

  • pre_start, pre_end: The boundaries for the current preorder subarray.
  • in_start, in_end: The boundaries for the current inorder subarray.

To speed up the .index() call, what if we pre-process the inorder array just once at the very beginning? We could build a hash map from value -> index. This would make finding the root’s index an O(1) lookup.

Let’s structure the optimised approach:

  1. Main Function build(preorder, inorder):

    • Create a value_to_inorder_index map from the inorder array.
    • Call the recursive helper with the initial full boundaries: build_helper(0, len(preorder)-1, 0, len(inorder)-1).

  2. Recursive Helper build_helper(pre_start, pre_end, in_start, in_end):

    • Base Case: If pre_start > pre_end or in_start > in_end, the subarray is empty. Return None.
    • Find Root: root_val = preorder[pre_start]. Create the root = TreeNode(root_val).
    • Find Partition Point: root_inorder_idx = value_to_inorder_index[root_val]. This is now O(1).
    • Calculate Left Subtree Size: left_subtree_size = root_inorder_idx - in_start. This is the crucial calculation.
    • Recurse Left:
      • The left inorder part is from in_start to root_inorder_idx - 1.
      • The left preorder part starts right after the root (pre_start + 1) and goes for left_subtree_size elements.
      • root.left = build_helper(…)
    • Recurse Right:
      • The right inorder part is from root_inorder_idx + 1 to in_end.
      • The right preorder part starts right after the left preorder part.
      • root.right = build_helper(…)
    • Return root.

got it so here is my attempt to solve this problem

class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


pre_order = [3,9,20,15,7]
in_order = [9,3,15,20,7]

def construct_bt_pre_in_order(pre_order, in_order):
	# create a hashmap for O(1) lookup of root indexes in inorder array
	index_lookup_in_inorder = {}
	for index,val in enumerate(in_order):
		index_lookup_in_inorder.update({val:index})
	
	def build_helper(pre_start, pre_end, in_start, in_end):
		# Base case if the array is empty
		if pre_start > pre_end or in_start > in_end:
			return None
		
		root = TreeNode(pre_order[start])
		root_index_in_in_order = index_lookup_in_inorder[root]
		left_subtree_size = root_index_in_in_order - in_start
		left_in_order_end =  root_index_in_in_order -1
		left_pre_order_start = pre_start +1 
		right_in_order_start = root_index_in_in_order + 1
		right_pre_order_start = left_pre_order+ left_subtree_size - 1
		root.left = build_helper(left_pre_order_start,left_subtree_size,in_start, left_in_order_end)
		root.right = build_helper( right_pre_order_start+1,pre_end ,right_in_order_start, in_end)
		
		return root
		
	
	binary_tree = build_helper(0,len(pre_order)-1, 0, len(in_order)-1)
	
	return binary_tree


tree = construct_bt_pre_in_order(pre_order, in_order)
  • 🥤 (pomodoro::BREAK) (duration:: 15m) (begin:: 2025-12-16 12:01) - (end:: 2025-12-16 12:16)

You are just getting tangled up in the final index calculations for the recursive calls, which is extremely common. Let’s break it down clearly.

State before recursive calls:

  • pre_start: Start of preorder slice.
  • in_start: Start of inorder slice.
  • root_val = preorder[pre_start]
  • root_inorder_idx: Index of root_val in the full inorder array.
  • left_subtree_size = root_inorder_idx - in_start

Let’s Define the Boundaries for the LEFT Subtree:

  • Inorder: The inorder for the left subtree is easy. It starts at in_start and ends just before the root.

    • in_start_left = in_start
    • in_end_left = root_inorder_idx - 1

  • Preorder: The preorder for the left subtree starts right after the root in the preorder array.

    • pre_start_left = pre_start + 1
    • How long is it? It’s left_subtree_size elements long. So it ends at pre_start + left_subtree_size.
    • pre_end_left = pre_start + left_subtree_size

Now, Let’s Define the Boundaries for the RIGHT Subtree:

  • Inorder: The inorder for the right subtree starts right after the root.

    • in_start_right = root_inorder_idx + 1
    • in_end_right = in_end

  • Preorder: The preorder for the right subtree starts right after the preorder for the left subtree ends.

    • The left subtree’s preorder ended at pre_start + left_subtree_size.
    • So, pre_start_right = pre_start + left_subtree_size + 1.
    • It goes all the way to the end of the current preorder slice.
    • pre_end_right = pre_end

Attempt 2

class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


pre_order = [3,9,20,15,7]
in_order = [9,3,15,20,7]

def construct_bt_pre_in_order(pre_order, in_order):
	# create a hashmap for O(1) lookup of root indexes in inorder array
	index_lookup_in_inorder = {}
	for index,val in enumerate(in_order):
		index_lookup_in_inorder.update({val:index})
	
	def build_helper(pre_start, pre_end, in_start, in_end):
		# Base case if the array is empty
		if pre_start > pre_end or in_start > in_end:
			return None
		
		root = TreeNode(pre_order[pre_start])
		root_index_in_in_order = index_lookup_in_inorder[root.val]
		left_subtree_size = root_index_in_in_order - in_start
		# The inorder for the left subtree is easy. It starts at in_start and ends just before the root.
		in_start_left = in_start
		in_end_left = root_index_in_in_order -1
		# Preorder: The preorder for the left subtree starts right after the root in the preorder array.
		pre_start_left = pre_start +1
		pre_end_left = pre_start + left_subtree_size
		# **Inorder:** The inorder for the right subtree starts right after the root.
		in_start_right = root_index_in_in_order + 1
		in_end_right = in_end
		# **Preorder:** The preorder for the right subtree starts right after the preorder for the left 
		pre_start_right = pre_start + left_subtree_size + 1
		pre_end_right = pre_end
		root.left = build_helper(pre_start_left, pre_end_left, in_start_left,in_end_left)
		root.right = build_helper(pre_start_right,pre_end_right, in_start_right, in_end_right)
		
		return root
		
	
	binary_tree = build_helper(0,len(pre_order)-1, 0, len(in_order)-1)
	
	return binary_tree


tree = construct_bt_pre_in_order(pre_order, in_order)
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-16 12:16) - (end:: 2025-12-16 12:46)