GFG🌳 Binary Tree Construction 🏗️ from Inorder and Postorder||Day 54||C++||Easy||Amazon||Microsoft

Step 1: Base Case Check 🧮

If n (number of nodes) is 0, return nullptr to indicate an empty tree.
Step 2: Finding the Root 🔍

Iterate over the inorder traversal (in array) to find the index of the root node (which is the last element in the postorder traversal post). This index divides the inorder traversal into left and right subtrees.
Step 3: Creating the Root Node 🌱

Create a new node with the value of the root (which is the last element in the postorder traversal) and store it in the root variable.
Step 4: Building the Left Subtree 🌿

Recursively build the left subtree using the buildTree function with the inorder traversal array (in), the postorder traversal array (post), and the size of the left subtree (which is rootIndex).
Step 5: Building the Right Subtree 🍂

Recursively build the right subtree using the buildTree function with the inorder traversal array starting from rootIndex + 1 (since we've already processed the root and its left subtree), the postorder traversal array starting from post + rootIndex (since the left subtree's elements are before the root in postorder), and the size of the right subtree (n - rootIndex - 1).
Step 6: Connecting the Subtrees 🌐

Connect the left and right subtrees to the root node by setting the left and right pointers of the root node to the leftSubtree and rightSubtree, respectively.
Step 7: Return Root 🎯

Return the root node of the constructed binary tree.
This algorithm works because the last element in the postorder traversal is always the root of the current subtree being processed. By finding this root in the inorder traversal, we can separate the elements into left and right subtrees, allowing us to recursively build the left and right subtrees of the current node.

#leetcode #geeksforgeeks #geek #learning #amazing #algorithm#tcs
#microsoft #deloitte #codinginterview #programming

Видео GFG🌳 Binary Tree Construction 🏗️ from Inorder and Postorder||Day 54||C++||Easy||Amazon||Microsoft канала Code With Deepa