Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python

0:00 - Read the problem
3:50 - Drawing Explanation
12:33 - Coding Explanation

leetcode 105

#sorted #array #python

[stupidfrog]

Easily the hardest 'Medium' I have ever seen. If you didn't get this one, don't be discouraged. Just get really good at recursive thinking and come back to it later.

[symbol]

This is the type of problem you give someone you don't want to hire...

[THEAVISTER]

Thanks for all your help NeetCode and all the effort you put into teaching concepts thoroughly!!

[blitzspirit]

Storing the index for mid in the hash map would be more efficient IMO. That would lead to time complexity O(n) otherwise it's O(n^2). Adding a section of time complexity is what's missing in most videos. IFF possible, please create time complexity videos for Neet75 and add the pertinent links in the description. That would be super helpful for people who are only using these videos to learn about the right approach to solving these problems.

```
# 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
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

# takes the left and right bound of inorder, logic --> any given inorder index bisects the tree in left and right subtree
def localBuildTree(leftBound, rightBound):
nonlocal preOrderListIndex

if leftBound > rightBound:
return None

newRootVal = preorder[preOrderListIndex]
newRoot = TreeNode(newRootVal)

preOrderListIndex += 1


newRoot.left = localBuildTree(leftBound,
newRoot.right = localBuildTree(inorderIndexFor[newRootVal]+1, rightBound)


return newRoot


inorderIndexFor = dict()
for index, element in enumerate(inorder):
inorderIndexFor[element] = index

preOrderListIndex = 0

return localBuildTree(0, len(preorder)-1)
```

[darhkz]

4:45. The 2nd value in preorder is not guaranteed to be the left node because it might not have a left node. What is guaranteed is in preorder = [root, [leftSubTreeValues], [rightSubTreeValues]]. A node's left subtree values come before its right subtree values in preorder traversal if looking at it in array form.

[pekarna]

Hi, this is stated MEDIUM but I think it's quite HARD.
Anyway, I have an improvement:
The lookup of the "pivot" in the Inorder array makes this order of magnitude more complex. The worst case around O(n^2).
I took an approach of keeping a stack, whose top tells me if I should close the current subtree. It is O(n).
The code as it is is not pleasing to look at, but works:

fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
if (preorder.isEmpty()) return null

var curI = 0
val root = TreeNode(preorder[0])
val stack = Stack<Int>().apply { this.add(preorder[0]) }
var curP = 1

fun hasNext() = curI < inorder.size && curP < preorder.size
fun nextInorder() = if (curI >= inorder.size) null else inorder[curI]
fun stackPeekOrNull() = if (stack.isEmpty()) null else stack.peek()

fun dfs(curNode: TreeNode) {

if (hasNext() && nextInorder() != curNode.`val`) {
curNode.left = TreeNode(preorder[curP++])

dfs(curNode.left!!)
}
if (nextInorder() == curNode.`val`) {
curI++
stack.pop()
if (curI >= inorder.size) return
}
if (nextInorder() == stackPeekOrNull()) {
return
}
if (nextInorder() != curNode.`val` && nextInorder() != stackPeekOrNull()) {
curNode.right = TreeNode(preorder[curP++])

dfs(curNode.right!!)
}
}

dfs(root)

return root
}

[MohamedAtef-dept]

Your ability to explain complex topics so clearly is truly impressive! Your content makes learning so much easier, and I appreciate the effort you put into sharing your knowledge. Thank you for your amazing work!🙏

[theanguyen]

Thank you. This is very easy to understand. You saved me from sitting at the computer for 5 hours more.

[GNR]

Lot of people are saying it's a hard problem and I agree.

However, with strong foundation in divid-and-conquer pattern (merge and quick sort helps) AND dfs tree traversal (inorder, preorder, postorder), this problem becomes very intuitive and the different approaches to the solution makes a LOT of sense!

[dansun]

I was also just going through this problem, I really like watching your videos, please keep posting!

[leonscander]

God damn. I was about to give up, but I solved it.
I was trying to come up with a brute force solution and the key moments that helped me during my thought process were:
1. Noticing that the first element in preorder is always a root node.
2. Noticing that everything to the left of the root value in inorder list is a left subtree and everything to the right is a right subtree.
3. Then you just need to figure out how to apply a recursion to above 2 statements to build the left and right subtrees.

[tarandeepsingh]

Yo man this is the easiest explanation I found on the internet
you gained a sub

[sheexcel]

But the time and space complexity are both O(n^2) because of the inorder.index() function and passing subarrays of preorder/inorder in each stack of the recursion.

[mannemsrinivas]

Instead of mid, If we rename it to leftTreeLength then we can understand the partitions very easily

[anabildebnath]

This is a very comprehensive explanation of a somewhat complex approach that makes the idea easier to grasp

[gregwhittier]

I don't think it's explicitly stated here (apologies if it is), but not only is the root the first element of the preorder, but all the left subtree items come before the right subtree which is way taking the first mid items only gets left subtree values. And buildtree recursing in preorder (root, left, right) is necessary. This is my mod to use a hashmap and indexing to get linear time.

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

inorder_idx_by_val = {inorder[i]:i for i in range(len(inorder))}

def _buildTree(pi, pj, ii, ij):

if (pi > pj) or (ii > ij):
return None

node = TreeNode(val=preorder[pi])
mid = inorder_idx_by_val[node.val]
node.left = _buildTree(pi+1, pi+(mid-ii), ii, mid-1)
node.right = _buildTree(pi+(mid-ii)+1, pj, mid+1, ij)

return node

return _buildTree(0, len(preorder)-1, 0, len(inorder)-1)

Your channel is awesome and thanks for putting all this out there.

[OMFGallusernamesgone]

How are you using mid from the inorder subarray to slice the preorder?

[zl]

One issue with this approach (on an edge case): if the tree is nearly vertical (width 1 each level, randomly left or right), then .index would take O(n) time on average and O(n^2) total. This can be avoided in an iterative method w/ hashmap.

[ritteshpv]

Python Code | much more efficient solution in time and space | Improvised from neetcode solution | Must read

Improvements:
1. Create a hashmap to retrieve index
2. Pass current interval of preorder and inorder instead of slicing

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

def r_build_tree(preorder_left, preorder_right, inorder_left):
if preorder_left == preorder_right:
return None

nonlocal inorder_hash_map
inorder_root_index = - inorder_left

root =
root.left = r_build_tree(preorder_left + 1, preorder_left + inorder_root_index + 1, inorder_left)
root.right = r_build_tree(preorder_left + inorder_root_index + 1, preorder_right, inorder_left + inorder_root_index + 1)

return root

inorder_hash_map = {}
for index, node in enumerate(inorder):
inorder_hash_map[node] = index

return r_build_tree(0, len(preorder), 0)

[abhineetsharma]

Thanks for the explanation, it was really helpful. You are the Mr.Miyagi of Competitive Coding. P.S: Please keep posting !