{"id":410,"date":"2024-04-14T21:19:00","date_gmt":"2024-04-14T20:19:00","guid":{"rendered":"https:\/\/noiseonthenet.space\/noise\/?p=410"},"modified":"2024-04-18T17:27:47","modified_gmt":"2024-04-18T16:27:47","slug":"climbing-a-binary-tree","status":"publish","type":"post","link":"https:\/\/noiseonthenet.space\/noise\/2024\/04\/climbing-a-binary-tree\/","title":{"rendered":"Climbing a (binary) Tree"},"content":{"rendered":"

\"annie-spratt-gNI4_88t9Rs-unsplash_reduced.jpg\" <\/p> <\/div>\n\n

Photo by Annie Spratt<\/a> on Unsplash<\/a> <\/p>\n\n

In this post I will show how to transform a recursive depth first traversal function into an iterator for a binary tree <\/p>\n\n

The complete source code for this post is available here<\/a>. <\/p>\n\n

After a couple of digressions we’re back to my beloved tree; here are the link of our journey so far: <\/p>\n\n

    \n
  1. Growing a (binary)Tree<\/a><\/li>\n
  2. Growing a (sorting) Tree<\/a><\/li>\n
  3. Stacking Bits<\/a><\/li>\n
  4. Prime Time<\/a><\/li>\n<\/ol>\n\n

    While in previous posts we traversed and print the content of the tree data structure with a recursive function, this may not be very convenient in the general case: what can we do to make it more general? <\/p>\n\n

      \n
    1. pass a lambda argument to the recursive traversal function<\/li>\n
    2. transform the traversal function into an iterator coroutine<\/li>\n<\/ol>\n\n

      The second approach leverage the whole Rust iterator interface, providing an easy connection with other data structures. <\/p>\n

      \n

      Fixing our tree<\/h2>\n
      \n

      Let’s first recall our previous implementation with some small fixes: first is to have a public tree interface which clearly separates from nodes <\/p>\n\n

      \n
      use<\/span> std<\/span>::fmt<\/span>::Debug<\/span>;\n\n#<\/span>[<\/span>derive<\/span>(<\/span>Debug<\/span>)<\/span>]<\/span>\npub<\/span> struct<\/span> Node<\/span><<\/span>T<\/span>>{<\/span>\n    value<\/span> : T<\/span>,\n    left<\/span> : Option<\/span><<\/span>Box<\/span><<\/span>Node<\/span><<\/span>T<\/span>><\/span>><\/span>><\/span>,\n    right<\/span> : Option<\/span><<\/span>Box<\/span><<\/span>Node<\/span><<\/span>T<\/span>><\/span>><\/span>><\/span>\n}<\/span>\n\nimpl<\/span><<\/span>T<\/span>><\/span> Node<\/span><<\/span>T<\/span>>{<\/span>\n    fn<\/span> new<\/span>(<\/span>value<\/span> : T<\/span>)<\/span> -> Node<\/span><<\/span>T<\/span>>{<\/span>\n        Node<\/span>{<\/span>\n            value,\n            left<\/span> : None<\/span>,\n            right<\/span> : None<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n\n#<\/span>[<\/span>derive<\/span>(<\/span>Debug,Default<\/span>)<\/span>]<\/span>\npub<\/span> struct<\/span> Tree<\/span><<\/span>T<\/span>>{<\/span>\n    root<\/span>: Option<\/span><<\/span>Box<\/span><<\/span>Node<\/span><<\/span>T<\/span>><\/span>><\/span>><\/span>\n}<\/span>\n\nimpl<\/span><<\/span>T<\/span>><\/span> Tree<\/span><<\/span>T<\/span>>{<\/span>\n    fn<\/span> new<\/span>()<\/span> -> Tree<\/span><<\/span>T<\/span>>{<\/span>\n        Tree<\/span>{<\/span>\n            root<\/span> : None<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n<\/pre>\n<\/div>\n\n
       the second fix is quite unnecessary but remove some boilerplate code when creating a node <\/p>\n\n
      \n