buildTreeFromInorderPreorder<T> function

BinaryTreeNode<T>? buildTreeFromInorderPreorder<T>(
  1. List<T> inorder,
  2. List<T> preorder
)

Implementation

BinaryTreeNode<T>? buildTreeFromInorderPreorder<T>(
  List<T> inorder,
  List<T> preorder,
) {
  if (inorder.isEmpty || preorder.isEmpty) return null;
  final Map<T, int> inorderIndex = {
    for (var i = 0; i < inorder.length; ++i) inorder[i]: i,
  };
  int preIndex = 0;
  BinaryTreeNode<T>? helper(int left, int right) {
    if (left > right) return null;
    final rootVal = preorder[preIndex++];
    final root = BinaryTreeNode<T>(rootVal);
    final idx = inorderIndex[rootVal]!;
    root.left = helper(left, idx - 1);
    root.right = helper(idx + 1, right);
    return root;
  }

  return helper(0, inorder.length - 1);
}