Skip to content

Add binary tree reconstruction from preorder + inorder #379

@0xDevNinja

Description

@0xDevNinja

Reconstruct a binary tree from its preorder + inorder traversals. (And, as a bonus variant, from postorder + inorder.) Both reconstructions are unique iff the tree has no duplicate values.

Algorithm: the first element of the preorder is the root. Find it in the inorder array; everything to its left forms the left subtree's inorder, everything to its right forms the right subtree's inorder. Split the preorder accordingly and recurse. Naive lookup is O(n²); a HashMap<value, inorder_index> precomputed once gives O(n) total.

API sketch

  • New module src/dynamic_programming/tree_from_traversals.rs (consider src/data_structures/ if a shared TreeNode lives there).
  • pub fn build_tree_pre_in<T: Eq + Hash + Clone>(preorder: &[T], inorder: &[T]) -> Option<Box<TreeNode<T>>>;
    pub fn build_tree_post_in<T: Eq + Hash + Clone>(postorder: &[T], inorder: &[T]) -> Option<Box<TreeNode<T>>>;
  • Reuse the TreeNode<T> defined for issue Add binary tree (owned, recursive) with traversals #324 (binary tree) when it lands. Returns None for inconsistent inputs (mismatched length, value in preorder not in inorder, duplicates).

Acceptance criteria

  • Module declared in the appropriate mod.rs.
  • Inline tests: empty / empty → None, single node, full balanced 7-node tree, left-skewed (preorder = inorder reversed pattern), right-skewed, random tree, mismatched-length inputs → None, duplicate values rejected (None or Err).
  • Property test: random tree of size ≤ 20 with distinct values — generate its preorder and inorder, reconstruct, verify the reconstructed tree is structurally equal to the original.
  • Doc comment cites the uniqueness condition (no duplicates) and gives O(n) with a position map.
  • cargo fmt --check, cargo clippy --all-targets -- -D warnings, cargo test pass.

Reference

Wu & Miller, Daily Coding Problem, Problem #48 — "Reconstruct tree from pre-order and in-order traversals".

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions