Skip to content

Add binary tree (owned, recursive) with traversals #324

@0xDevNinja

Description

@0xDevNinja

Add a public, owned BinaryTree<T> type backed by Box<Node<T>> with iterative pre-/in-/post-order and BFS level-order traversals. The repo currently has no first-class binary tree — Trie and SegmentTree use slabs/Vec-backed layouts; this module is the foundation for the rest of the v0.13.0 binary-tree issues.

API sketch

  • pub struct BinaryTree<T> { root: Option<Box<Node<T>>> }, Node { value: T, left, right }.
  • pub fn empty(), from_value(T), with_children(value, left, right), is_empty, height() -> usize, len() -> usize.
  • Traversals returning Vec<T> for T: Clone: preorder, inorder, postorder, level_order (BFS using VecDeque<&Node<T>>).
  • Iterative implementations (avoid unsafe; use explicit stacks).

Acceptance criteria

  • Implementation lives in src/data_structures/binary_tree.rs and is declared in src/data_structures/mod.rs.
  • Inline #[cfg(test)] mod tests covers empty, single node, left-only chain, right-only chain, perfect tree of height 3 (verifies all four traversal orders), and unbalanced tree.
  • Property test (quickcheck) on randomly built trees: preorder.len() == inorder.len() == postorder.len() == level_order.len() == len().
  • Doc comment names the four traversal orders and gives complexity (O(n) each).
  • cargo fmt --check, cargo clippy --all-targets -- -D warnings, and cargo test all pass.

References

Mongan, Programming Interviews Exposed, Ch. 3 (Trees and Graphs).

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions