Construct Binary Tree from Preorder and Inorder Traversal

1. Problem Description

Construct a binary tree from its preorder traversal and inorder traversal.

2. Approach

1. Approach 1
   • The first element of preorder traversal is the root
   • Use the root’s position in inorder traversal to split inorder into two parts: the left part corresponds to the left subtree and the right part corresponds to the right subtree
   • Note that this is not necessarily a binary search tree, so the inorder traversal is not sorted

3. Implementation

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 { return nil }
    rootVal := preorder[0]
    idx := find(inorder, rootVal)
    root := &TreeNode{Val: rootVal}
    root.Left = buildTree(preorder[1:idx+1], inorder[:idx])
    root.Right = buildTree(preorder[idx+1:], inorder[idx+1:])
    return root
}

func find(nums []int, target int) int {
    for i, num := range nums {
        if num == target { return i }
    }
    return -1
}

4. References

• Construct Binary Tree from Preorder and Inorder Traversal - LeetCode