Construct Binary Tree From Inorder And Postorder Traversal

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); ++i) {
            inorder_map[inorder[i]] = i;
        }
        return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorder_map);
    }
    
    TreeNode* buildTreeHelper(vector<int>& inorder, int in_start, int in_end, vector<int>& postorder, int post_start, int post_end, unordered_map<int, int>& inorder_map) {
        if (in_start > in_end || post_start > post_end) {
            return nullptr;
        }
        
        int root_val = postorder[post_end];
        TreeNode* root = new TreeNode(root_val);
        
        int root_idx = inorder_map[root_val];
        int left_size = root_idx - in_start;
        
        root->left = buildTreeHelper(inorder, in_start, root_idx - 1, postorder, post_start, post_start + left_size - 1, inorder_map);
        root->right = buildTreeHelper(inorder, root_idx + 1, in_end, postorder, post_start + left_size, post_end - 1, inorder_map);
        
        return root;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTreeHelper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int postEnd, int inStart, int inEnd) {
        if (inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd]);
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }

        root.right = buildTreeHelper(inorder, postorder, postEnd - 1, inIndex + 1, inEnd);
        root.left = buildTreeHelper(inorder, postorder, postEnd - (inEnd - inIndex) - 1, inStart, inIndex - 1);

        return root;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    if(inorderSize == 0) return NULL;
    
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = postorder[postorderSize - 1];
    
    int idx = 0;
    for(int i = 0; i < inorderSize; i++) {
        if(inorder[i] == root->val) {
            idx = i;
            break;
        }
    }
    
    root->left = buildTree(inorder, idx, postorder, idx);
    root->right = buildTree(inorder + idx + 1, inorderSize - idx - 1, postorder + idx, postorderSize - idx - 1);
    
    return root;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        return BuildTreeHelper(inorder, postorder, 0, inorder.Length - 1, 0, postorder.Length - 1);
    }
    
    private TreeNode BuildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        
        int rootValue = postorder[postEnd];
        TreeNode root = new TreeNode(rootValue);
        
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootValue) {
                inIndex = i;
                break;
            }
        }
        
        int leftSize = inIndex - inStart;
        
        root.left = BuildTreeHelper(inorder, postorder, inStart, inIndex - 1, postStart, postStart + leftSize - 1);
        root.right = BuildTreeHelper(inorder, postorder, inIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
        
        return root;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 */

var buildTree = function(inorder, postorder) {
    const build = (inStart, inEnd, postStart, postEnd) => {
        if (inStart > inEnd || postStart > postEnd) return null;
        
        const rootVal = postorder[postEnd];
        const root = new TreeNode(rootVal);
        
        let inIndex = inorder.indexOf(rootVal);
        let leftSize = inIndex - inStart;
        
        root.left = build(inStart, inIndex - 1, postStart, postStart + leftSize - 1);
        root.right = build(inIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
        
        return root;
    };
    
    return build(0, inorder.length - 1, 0, postorder.length - 1);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    if (inorder.length === 0 || postorder.length === 0) {
        return null;
    }
    
    const rootVal = postorder.pop()!;
    const root = new TreeNode(rootVal);
    
    const rootIndex = inorder.indexOf(rootVal);
    
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder);
    root.left = buildTree(inorder.slice(0, rootIndex), postorder);
    
    return root;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */

class Solution {

    private $inorderIndexMap;
    private $postorder;
    private $inorder;

    function buildTree($inorder, $postorder) {
        $this->postorder = $postorder;
        $this->inorder = $inorder;

        $this->inorderIndexMap = array_flip($inorder);
        return $this->build(0, count($inorder) - 1, 0, count($postorder) - 1);
    }

    function build($inorderStart, $inorderEnd, $postorderStart, $postorderEnd) {
        if ($postorderStart > $postorderEnd) {
            return null;
        }

        $rootValue = $this->postorder[$postorderEnd];
        $root = new TreeNode($rootValue);

        $index = $this->inorderIndexMap[$rootValue];

        $numLeft = $index - $inorderStart;
        $root->left = $this->build($inorderStart, $index - 1, $postorderStart, $postorderStart + $numLeft - 1);
        $root->right = $this->build($index + 1, $inorderEnd, $postorderStart + $numLeft, $postorderEnd - 1);

        return $root;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    var index = [Int: Int]()

    func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        for (index, num) in inorder.enumerated() {
            self.index[num] = index
        }
        return buildNode(inorder, 0, inorder.count - 1, postorder, 0, postorder.count - 1)
    }

    func buildNode(_ inorder: [Int], _ inStart: Int, _ inEnd: Int, _ postorder: [Int], _ postStart: Int, _ postEnd: Int) -> TreeNode? {
        if inStart > inEnd || postStart > postEnd {
            return nil
        }
        let rootVal = postorder[postEnd]
        let rootIndex = index[rootVal]!

        let root = TreeNode(rootVal)
        let leftSize = rootIndex - inStart
        root.left = buildNode(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1)
        root.right = buildNode(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1)

        return root
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(inorder) == 0 {
        return nil
    }
    
    rootVal := postorder[len(postorder)-1]
    root := &TreeNode{Val: rootVal}
    
    i := 0
    for ; i < len(inorder); i++ {
        if inorder[i] == rootVal {
            break
        }
    }
    
    root.Left = buildTree(inorder[:i], postorder[:i])
    root.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1])
    
    return root
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left, @right = left, right
#     end
# end

def build_tree(inorder, postorder)
    return nil if inorder.empty?
    
    root_val = postorder.pop
    root_index = inorder.index(root_val)
    
    root = TreeNode.new(root_val)
    
    root.right = build_tree(inorder[root_index + 1..-1], postorder)
    root.left = build_tree(inorder[0...root_index], postorder)
    
    root
end

                                            
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        fn helper(inorder: &[i32], postorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
            if postorder.is_empty() {
                return None;
            }
        
            let root_val = postorder[postorder.len() - 1];
            let mut root = TreeNode {
                val: root_val,
                left: None,
                right: None,
            };
        
            let mut inorder_idx = 0;
            while inorder[inorder_idx] != root_val {
                inorder_idx += 1;
            }
        
            let inorder_left = &inorder[..inorder_idx];
            let inorder_right = &inorder[inorder_idx + 1..];
        
            let postorder_left = &postorder[..inorder_idx];
            let postorder_right = &postorder[inorder_idx..postorder.len() - 1];
        
            root.left = helper(inorder_left, postorder_left);
            root.right = helper(inorder_right, postorder_right);
        
            Some(Rc::new(RefCell::new(root)))
        }
    
        helper(&inorder, &postorder)
    }
}

To solve this coding challenge of reconstructing a binary tree from its inorder and postorder traversals, we need to understand how both traversal types work:

Inorder Traversal (Left, Root, Right): This means for any node, we visit all nodes in its left subtree first, then the node itself, and finally all nodes in its right subtree.
Postorder Traversal (Left, Right, Root): This means for any node, we visit all nodes in its left subtree first, then all nodes in its right subtree, and finally the node itself.

The key point to solving this challenge is to recognize that in postorder traversal, the last element is the root of the binary tree.

Explanation

Identify the Root : The last element in the postorder array is the root of the tree.
Find the Root in Inorder Array : Using this root value, locate its index in the inorder array. Elements to the left in the inorder array are part of the left subtree, and elements to the right are part of the right subtree.
Recursive Construction : Recursively apply the process to the left and right subtrees, using the corresponding slices of the inorder and postorder arrays.

Detailed Steps in Pseudocode

Base Case : If the range for the inorder or postorder array is invalid (start index greater than end index), return
null

.
Identify the Root :

The root value is the last element in the current range of the postorder array.
Create a new tree node with this root value.

Find Split Point :

Locate the root value's index in the inorder array. This will determine the boundaries of the left and right subarrays.
The number of elements in the left subtree can be calculated as the difference between the root index in the inorder array and the starting index of the current inorder range.

Recursive Calls :

Recursively build the left subtree with the respective ranges in the inorder and postorder arrays.
Recursively build the right subtree with the respective ranges in the inorder and postorder arrays.

Combine : Assign the recursively built left and right subtrees to the root node.

Below is the pseudocode embodying these steps:

                                            
# Pseudocode for constructing the binary tree from inorder and postorder traversals

# Function to build tree
FUNCTION buildTree(inorder, postorder):
    
    # Helper function to construct the tree
    FUNCTION build(inStart, inEnd, postStart, postEnd):
        
        # Base case: if no elements to consider in the current segment, return null
        IF inStart > inEnd OR postStart > postEnd:
            RETURN null
        
        # The root value is the last element in the current segment of the postorder array
        rootValue = postorder[postEnd]
        
        # Create a new tree node with the root value
        root = new TreeNode(rootValue)
        
        # Find the index of root value in the inorder array
        inIndex = FIND_INDEX(inorder, rootValue)
        
        # Determine the size of the left subtree
        leftSize = inIndex - inStart
        
        # Recursively build the left subtree
        root.left = build(inStart, inIndex - 1, postStart, postStart + leftSize - 1)
        
        # Recursively build the right subtree
        root.right = build(inIndex + 1, inEnd, postStart + leftSize, postEnd - 1)
        
        # Return the constructed tree node
        RETURN root
    
    # Call the helper function with the entire range of both arrays
    RETURN build(0, LENGTH(inorder) - 1, 0, LENGTH(postorder) - 1)

In this pseudocode:

The base case handles the scenario when an invalid range is encountered, ensuring the recursion terminates correctly.
The
FIND_INDEX

function is abstracted to mean acquiring the index of the root value in the inorder array.
The calculation of
leftSize

helps in determining the boundary of subarrays for the next level of recursive calls.

By following this detailed methodology and breaking down each step, one can systematically build the binary tree from given inorder and postorder traversals. This also ensures that the solution is both comprehensive and easy to follow, enhancing the clarity of the logic involved in the construction process.