Solving Construct Binary Tree from Preorder and Inorder Traversal

The "Construct Binary Tree from Preorder and Inorder Traversal" problem involves rebuilding a binary tree from its preorder and inorder traversal sequences.

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example

• Preorder: [3,9,20,15,7]
• Inorder: [9,3,15,20,7]

The constructed binary tree is:

Solution Approach - Recursive Construction

Breaking Down the Solution

• Map for Inorder Indices: Create a map to quickly find the index of each value in the inorder sequence.
• Recursive Construction: Recursively build the left and right subtrees using the indices in the map to find the dividing point.
• Preorder Traversal: The preorder array guides the creation of each node, starting from the root.

Conclusion

Constructing a binary tree from preorder and inorder traversals is an intriguing challenge that tests understanding of tree properties and traversal techniques.

Rust Solution

Because array_to_tree is a nested plain fn rather than a closure, it cannot capture surrounding state — pre_index, preorder, and in_map are each threaded through explicitly, with the shared cursor passed as &mut usize and the arrays as &[i32] slice borrows. The tree is modelled as Option<Box<TreeNode>>: Box supplies the heap indirection a self-referential struct needs, and None stands in for a missing child. in_map.get(&root_val).unwrap() yields a borrowed index that is dereferenced and cast with as i32 so it can be compared against the signed left/right bounds. Each node is handed back wrapped as Some(Box::new(root)).

Go Solution

arrayToTree is declared as a var of function type and assigned afterwards — the idiom Go requires so a recursive closure can refer to itself — and it then captures preIndex, preorder, and the map[int]int{} inMap straight from the enclosing buildTree, so nothing is threaded through as parameters the way Rust's nested fn demands. The index is built with for i, v := range inorder, and lookups use a bare idx := inMap[rootVal] rather than the comma-ok form, leaning on every preorder value being present. A missing child is the nil pointer return nil, and a node is &TreeNode{Val: rootVal} — a pointer to a composite literal whose unset Left/Right fields default to nil.