search

DivyaGodayal / CoderChef-Kitchen

The official repository for our programming kitchen which consists of 50+ delicious programming recipes having all the interesting ingredients ranging from dynamic programming, graph theory, linked lists and much more. All the articles contain beautiful images and some gif/video at times to help clear important concepts.
373 stars 82 forks source link

Tree Construction #105

Closed Arihant1467 closed 5 years ago

Arihant1467 commented 5 years ago

Completed the construction of tree from inorder and postorder traversal

edorado93 commented 5 years ago

Hey @Arihant1467, the article looks great. I will review it later today. Can you by any chance add a Java/C++ (whatever you are comfortable with) solution as well? If that would take time, you can take it up later. But if it's no biggie, can you add it to this PR?

Arihant1467 commented 5 years ago

Sure bro. I will do that. I will add it to this PR. Give me a day or two to write it properly.

Thanks

On Sat, Feb 23, 2019 at 7:45 PM Sachin Malhotra notifications@github.com wrote:

Hey @Arihant1467 https://github.com/Arihant1467, the article looks great. I will review it later today. Can you by any chance add a Java/C++ (whatever you are comfortable with) solution as well? If that would take time, you can take it up later. But if it's no biggie, can you add it to this PR?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#issuecomment-466731022, or mute the thread https://github.com/notifications/unsubscribe-auth/AKiRztC5Ha6wZ9zEW8ntg3Et6KGL4wVKks5vQgr0gaJpZM4bOUAF .

edorado93 commented 5 years ago

Sure @Arihant1467, I'll review the PR in the meantime and suggest changes if any. Will merge it once we have the Java solution as well. Thanks!

Arihant1467 commented 5 years ago

Give me few days. I will complete all the prosposed changes and add the "indices" solution as a second approach to the to current solution.

On Sun, Feb 24, 2019, 09:20 Sachin Malhotra <notifications@github.com wrote:

@edorado93 requested changes on this pull request.

rootNode.left = self.buildTree(inorder[:index],postorder[0:index]) rootNode.right = self.buildTree(inorder[index+1:],postorder[index:-1])

I think we can optimize this further. So there are two optimizations that I can think of right now. The overall algorithm would remain the same but implementation and complexity wise we can tweak stuff a bit.

  1. Since the tree doesn't have duplicate values, we can create a hash map initially that maps a node value to its index in the inorder traversal. That way, you won't need to do a linear search for it in every recursion. The space complexity would still be O(N) but the time complexity would come down to O(N) now.
  2. The second optimization is that you don't need to pass a subarray every time to the recursive call. Creating a subarray is also an O(N) operation. You can make do with the original array and a pair of indices left and right as well which tell you the range of the current subarray. So, instead of passing a subarray, just pass indices.

index = postorder[-1] rootNode.left = self.buildTree(inorder_left, index - 1, postorder_left, index - 1) rootNode.right = self.buildTree(index + 1, inorder_right, index, postorder_right - 1)

You'll definitely get a speed boost with this. You can either update the current code and add this portion to the algorithm and update the complexity analysis OR you can add an approach 2 and point out these optimizations in there and add the corresponding algorithm and complexity analysis. I leave that upto you.

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630206 :

@@ -0,0 +1,52 @@ +## Construct a Binary Tree from Inorder and Postorder Traversal + +

+Question Screenshot

Can we change the folder name from Tree-Construction to Binary-Tree-from-Inorder-and-Postorder-Traversal. I know this is a long-ish name but I feel we should try and keep the original problem names as folder names as much as possible.

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630255 :

@@ -0,0 +1,52 @@ +## Construct a Binary Tree from Inorder and Postorder Traversal + +

+Question Screenshot +

+ +--- + +### Solution : + +#### Motivation +We are given inorder and postorder traversal of a Binary Tree and we have to recreate the Binary Tree from the given traversals. + +TIP: To create a binary tree we need atleast two different traversals. A single traversal can have many different tree structures.

A single traversal can have correspond to

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630266 :

+## Construct a Binary Tree from Inorder and Postorder Traversal + +

+Question Screenshot +

+ +--- + +### Solution : + +#### Motivation +We are given inorder and postorder traversal of a Binary Tree and we have to recreate the Binary Tree from the given traversals. + +TIP: To create a binary tree we need atleast two different traversals. A single traversal can have many different tree structures. + +Let us understand how are we gonna approach the problem by taking an example.

gonna going to

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630333 :

+Question Screenshot +

+ +--- + +### Solution : + +#### Motivation +We are given inorder and postorder traversal of a Binary Tree and we have to recreate the Binary Tree from the given traversals. + +TIP: To create a binary tree we need atleast two different traversals. A single traversal can have many different tree structures. + +Let us understand how are we gonna approach the problem by taking an example. + +

+Question Screenshot

Reduce the size of the image. e.g.

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630379 :

+Let us understand how are we gonna approach the problem by taking an example. + +

+Question Screenshot +

+ +Let us write the Inorder and Postorder traversal of the above tree. + + +Inorder = [24,29,38,41,49,51,55,63,77] +Postorder = [29,24,41,38,51,55,77,63,49] + +#### Observations derived from the Tree structure and it's traversals : + +1. root of the tree will always be the last node in it's postorder traversal. +2. Nodes left to the root and Nodes right to the root appear in same fashion in it's inorder traversal. From the diagram Node(38) and Node(63) are left and right node of Root(49), they appear in same manner in the inorder traversal of the tree. They don`t change their relative order with respect to it's parent.

They don`t don't change

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630412 :

+Let us write the Inorder and Postorder traversal of the above tree. + + +Inorder = [24,29,38,41,49,51,55,63,77] +Postorder = [29,24,41,38,51,55,77,63,49] + +#### Observations derived from the Tree structure and it's traversals : + +1. root of the tree will always be the last node in it's postorder traversal. +2. Nodes left to the root and Nodes right to the root appear in same fashion in it's inorder traversal. From the diagram Node(38) and Node(63) are left and right node of Root(49), they appear in same manner in the inorder traversal of the tree. They dont change their relative order with respect to it's parent. + +#### Algorithm +1. Find the last node in thepostordertraversal. +2. Mark this as root for the current state. +3. Find the index of above node in theinordertraversal tree. So everything left to thatindexwill be the left subtree and right to theindex` will be the right subtree. +4. Recusrsively repeat the the process from step 1-3 for left and right subtree.

Recusrsively Recursively

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630459 :

+`` +#### Observations derived from the Tree structure and it's traversals : + +1.rootof the tree will always be the last node in it's postorder traversal. +2. Nodes left to therootand Nodes right to therootappear in same fashion in it's inorder traversal. From the diagram Node(38) and Node(63) are left and right node of Root(49), they appear in same manner in theinordertraversal of the tree. They dont change their relative order with respect to it's parent. + +#### Algorithm +1. Find the last node in the postorder traversal. +2. Mark this as root for the current state. +3. Find the index of above node in the inorder traversal tree. So everything left to that index will be the left subtree and right to the index will be the right subtree. +4. Recusrsively repeat the the process from step 1-3 for left and right subtree. + + + +#### Complexity Analysis +* Time Complexity: O(N^2) where N is the number of nodes. This is beacuse we are searching index of last node in postorder traversal in the inorder traversal of the tree.

traversal in the inorder traversal of the tree traversal in the inorder traversal of the tree for each recursive call

In Graphs-And-Trees/Tree-Construction/README.md https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#discussion_r259630521 :

+#### Algorithm +1. Find the last node in the postorder traversal. +2. Mark this as root for the current state. +3. Find the index of above node in the inorder traversal tree. So everything left to that index will be the left subtree and right to the index will be the right subtree. +4. Recusrsively repeat the the process from step 1-3 for left and right subtree. + + + +#### Complexity Analysis + Time Complexity: O(N^2) where N is the number of nodes. This is beacuse we are searching index of last node in postorder traversal in the inorder traversal of the tree. + Space Complexity: O(N) where N is the number of nodes. The space is occupied by the recursion stack in this case. + +#### Link to OJ +https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ + +#### Link to Solution

You can remove this. It's not a part of the standard template and I don't feel the need to add a link to a specific solution since they would be clearly visible on the page where README is located. So we can get rid of it.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/DivyaGodayal/CoderChef-Kitchen/pull/105#pullrequestreview-207161708, or mute the thread https://github.com/notifications/unsubscribe-auth/AKiRztSLaBmR_gYt5ZlONlv0nTYOS5KFks5vQsnzgaJpZM4bOUAF .

edorado93 commented 5 years ago

Sure @Arihant1467, thank you for the C++ solution 👍

Arihant1467 commented 5 years ago

Hey @edorado93, I made the requested changes and added an incremental solution approaches. I have also added cpp solutions to the approaches defined. Let me know if any changes are required to be made. I have made changes in same PR

edorado93 commented 5 years ago

Cool. I will take a look soon. Thanks!

edorado93 commented 5 years ago

Great job with the 3 incremental solutions @Arihant1467.

giphy