Construct Binary Tree from Preorder and Postorder Traversal - Leetcode 889 - Python

0:00 - Intro
0:40 - Drawing Explanation
12:00 - Dry Run
15:51 - Coding Explanation

leetcode 889

#neetcode #leetcode #python

[RhanThakur]

The simplest solution is often the best one! You're a boss of DSA

[jamestwosheep]

I managed to do this one with a slightly simpler solution that involved going through the preorder list iteratively and keeping the nodes on a stack.

Start by making a value->index lookup for the postorder array as you did in this video. Then, create the root node of the tree based on the first value of preorder, and push that node to the stack. Then for each subsequent value in preorder, while the postorder index of the node at the top of the stack comes before the postorder index of the current value, pop it from the stack as it cannot possibly be a parent of the current node. Once we have a node on the stack whose postorder index comes after the current value, we create the new node, assign it as a child of the node at the top of the stack (prioritising the left branch if it hasn't already been assigned), and then we push the new node onto the stack.

I get that my explanation might be a little difficult to parse without some diagrams to illustrate what I mean, but basically it was the way I managed to do this problem without a whole load of pointers.

[samifawcett]

right when you circled the 1 the solution came to me. have been trying to get it for hours. ty.

[Devilextremeful]

It took me a little while, but I was able to solve this by myself. It was definitely harder than the problem the day before. I like to compare solutions as usual thanks for your work.

[thall]

Thanks for sharing your thought process in the code comments, nice getting a behind the scenes like that

[ROHITKUMAR-ect]

14:06 Thank you for confirming, yes if yesterday's was Hard this should also be marked Hard. Labels do not make much sense.

[evergreen]

Made this look so simple ! Thanks man !

[mirkelor]

I solved it on my own by using stack. Simply add preorder values to the stack until they match with postorder index when they matched pop it and add it to the first non nil left or right of the last node in the stack

[drallersouldust]

just a maybe, I can learn and understand it

[ben_]

looks like i solved the other problem a year ago and couldn't get this one

[gabrielfonseca]

Stack solution:

let i be the pointer to preorder
let j be the pointer to postorder

When a node is found in the preorder array, it is either:
A direct child of the last element in the stack or
A new subtree

The values in postorder show the end of each subtree. Therefore:

Range through all items i in preorder. If the value at postorder[i] is the same as the last element in the stack, then we have reached the end of a subtree. Pop the element from the stack with a while loop and increment j each time. Otherwise, the new value is a child of the last element in the stack, so put it as a left child (or right child if left child already exists) and append to the stack.

Dry run of example 1:

stack [1] i = 1, j = 0 Tree = 1 at the start
stack[1, 2, 4] i = 3, j =0 Tree = 1 -> 2 -> 4. postorder[j] = 4 = stack[-1], so pop. append 5.
stack = [1, 2, 5] i = 4, j = 1 Tree = 1 -> 2 -> (4, 5). postorder[j] = 5, so pop. now postorder[j] = 2, so pop again (we have finished exploring the subtree rooted at 2). Finally, append 3.
The stack will be [1, 3, 6] when we find the next element in postorder, 6. This will be popped, and 7 added. On the next iteration, the loop will break (i will be out of bounds) with the stack as [1, 3, 7] with j = 4. All these nodes are explored, so if we continued we'd just pop them from the stack each time (the next elements in postorder are 7, 3, 1).

[saarthak]

Hey @NeetCode, can you make a video on todays hard problem in the leetcode contest (3463. Check If Digits Are Equal in String After Operations II), it has concepts like pascals triangle and lucas's theorem and it would be of great help if you explained it

[chaitanyayeole]

If anybody is wondering how to solve this problem in the same way as Leetcode 105.

class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not preorder or not postorder:
return None

il, ir = 0, len(preorder) - 1
jl, jr = 0, len(postorder) - 1

root = TreeNode(preorder[il])

if il + 1 <= ir or jl + 1 <= jr:
mid = postorder.index(preorder[il + 1])
else:
return root

root.left = + 2], postorder[:mid + 1])
root.right = + 2:ir + 1], postorder[mid + 1:jr])

return root

[Wasabi.Script]

this sht is so hard man i don't have the brain power

[oogieboogie]

Minimal code with less variables
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not preorder or not postorder:
return None
root = TreeNode(preorder[0])
preorder.pop(0)
postorder.pop()
if preorder:
left_idx = postorder.index(preorder[0])
root.left = self.constructFromPrePost(preorder[:left_idx+1], postorder[:left_idx+1])
root.right = self.constructFromPrePost(preorder[left_idx+1:], postorder[left_idx+1:])
return root

[qulinxao]

class Solution:
def constructFromPrePost(s, f: List[int], e: List[int]) -> Optional[TreeNode]:
if f: return TreeNode(f[0],
s.constructFromPrePost(f[1:(lf:=e.index(f[1]))+2], e[:lf+1])if f[1:] else None, , e[lf+1:-1]) if f[1:] else None)

[dankquan]

my dumb*ss was trying to solve this problem with your inorder video and it wasnt making any sense, came back the next day and realized I was watching the wrong solution video

[dusvn]

1:02 actually first version gives me pain 😂

[reginaldwilliamfrancis]

5:13 is actually gonna be...funny accent from our guy😂

[ManojKumar-jttj]

Bro doesn't run the code, he submits it 😆