Restore binary tree

Let’s define inorder and preorder traversals of a binary tree as follows:

• Inorder traversal first visits the left subtree, then the root, then its right subtree;
• Preorder traversal first visits the root, then its left subtree, then its right subtree.

For example, if tree looks like this:

    1
   / \
  2   3
 /   / \
4   5   6

then the traversals will be as follows:

• Inorder traversal: [4, 2, 1, 5, 3, 6]
• Preorder traversal: [1, 2, 4, 3, 5, 6]

Given the inorder and preorder traversals of a binary tree t, but not t itself, restore t and return it.

Example

• For inorder = [4, 2, 1, 5, 3, 6] and preorder = [1, 2, 4, 3, 5, 6], the output should be

  Copy

  solution(inorder, preorder) = {
      "value": 1,
      "left": {
          "value": 2,
          "left": {
              "value": 4,
              "left": null,
              "right": null
          },
          "right": null
      },
      "right": {
          "value": 3,
          "left": {
              "value": 5,
              "left": null,
              "right": null
          },
          "right": {
              "value": 6,
              "left": null,
              "right": null
          }
      }
  }

• For inorder = [2, 5] and preorder = [5, 2], the output should be

  Copy

  solution(inorder, preorder) = {
      "value": 5,
      "left": {
          "value": 2,
          "left": null,
          "right": null
      },
      "right": null
  }

• The first element in the preorder array is always the root node of the tree.
• We find the index of this root node in the inorder array.
• All the elements to the left of the root node in the inorder array are in the left subtree, and all the elements to the right of the root node in the inorder array are in the right subtree.
• We recursively call the buildTree function on the left and right subtrees, passing the appropriate inorder and preorder arrays for each subtree.

For inorder = [4, 2, 1, 5, 3, 6] and preorder = [1, 2, 4, 3, 5, 6]

• Get root from first element in the preorder array 1 then get index from inorder that contains 1. We got index 2 here.
• Create tree recursively

                    1
                  /    \
build([4,2], [2,4])    build([5, 3, 6], [3, 5, 6])

• Repeat step above and get new tree

                                 1
                  /                            \
                 2                              3
              /    \                          /    \
  build([4],[4])    build([],[])   build([5],[5])  build([6],[6])

• and the result is

    1
   / \
  2   3
 /   / \
4   5   6

Here the code:

package main

import "github.com/davecgh/go-spew/spew"

type Tree struct {
	Value interface{}
	Left  *Tree
	Right *Tree
}

func build(inorder []int, preorder []int) *Tree {
	if len(inorder) == 0 {
		return nil
	}

	root := preorder[0]
	rootIndex := 0

	for i, val := range inorder {
		if val == root {
			rootIndex = i
			break
		}
	}

	return &Tree{
		Value: root,
		Left:  build(inorder[:rootIndex], preorder[1:rootIndex+1]),
		Right: build(inorder[rootIndex+1:], preorder[rootIndex+1:]),
	}
}

func main() {
	tree := build([]int{4, 2, 1, 5, 3, 6}, []int{1, 2, 4, 3, 5, 6})
	spew.Dump(tree)
}

Try it your self https://go.dev/play/p/dFSASO4Js4c