{"id":357,"date":"2024-03-17T09:22:00","date_gmt":"2024-03-17T08:22:00","guid":{"rendered":"https:\/\/noiseonthenet.space\/noise\/?p=357"},"modified":"2024-03-24T21:42:59","modified_gmt":"2024-03-24T20:42:59","slug":"growing-a-sorting-tree","status":"publish","type":"post","link":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/","title":{"rendered":"Growing a (sorting) tree"},"content":{"rendered":"<div id=\"org6b65d33\" class=\"figure\">\n\n<img data-recalc-dims=\"1\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?ssl=1\" alt=\"jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg\" \/>\n\n<\/div>\nPhoto by <a href=\"https:\/\/unsplash.com\/@jaysoobs?utm_content=creditCopyText&amp;utm_medium=referral&amp;utm_source=unsplash\" data-bcup-haslogintext=\"no\">Jared Subia<\/a> on <a href=\"https:\/\/unsplash.com\/photos\/two-cherries-hanging-from-a-branch-with-leaves-TcDc9jLOjGU?utm_content=creditCopyText&amp;utm_medium=referral&amp;utm_source=unsplash\" data-bcup-haslogintext=\"no\">Unsplash<\/a>\n\nIn this post we will extend our binary tree using generics and trait constraint, and add a simple sorting algorithm based on depth first traverse.\n<div id=\"outline-container-orgd4596ad\" class=\"outline-2\">\n<h2 id=\"orgd4596ad\">Adding some fruit to our tree<\/h2>\n<div id=\"text-orgd4596ad\" class=\"outline-text-2\">\n\nIn a previous post <a href=\"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-binary-tree-in-rust\/\" data-bcup-haslogintext=\"no\">Growing a (binary) tree<\/a> I described what a binary tree is and how to create one in Rust.\n\nTo really have an useful tree we may want to add some content to the data structure. let\u2019s start with something simple: each node can host a 32 bit integer\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #51afef; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">derive<\/span><span style=\"color: #c678dd; font-weight: bold;\">(<\/span><span style=\"color: #51afef; font-weight: bold;\">Debug<\/span><span style=\"color: #c678dd; font-weight: bold;\">)<\/span><span style=\"color: #51afef; font-weight: bold;\">]<\/span>\n<span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">struct<\/span> <span style=\"color: #ecbe7b;\">BTree0<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #dcaeea;\">left<\/span> : <span style=\"color: #ecbe7b;\">Option<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ecbe7b;\">Box<\/span><span style=\"color: #98be65;\">&lt;<\/span><span style=\"color: #ecbe7b;\">BTree0<\/span><span style=\"color: #98be65;\">&gt;<\/span><span style=\"color: #c678dd;\">&gt;<\/span>,\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #dcaeea;\">right<\/span> : <span style=\"color: #ecbe7b;\">Option<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ecbe7b;\">Box<\/span><span style=\"color: #98be65;\">&lt;<\/span><span style=\"color: #ecbe7b;\">BTree0<\/span><span style=\"color: #98be65;\">&gt;<\/span><span style=\"color: #c678dd;\">&gt;<\/span>,\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #dcaeea;\">content<\/span> : <span style=\"color: #ecbe7b;\">i32<\/span>,\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nTrees are often built with a recursive function call, i.e. a function which calls itself. Of course there should be some way to limit this calls in order to avoid infinite loops. Let\u2019s start with a function which accepts two values:\n<ul class=\"org-ul\">\n \t<li>a maximum possible depth of our tree<\/li>\n \t<li>the current depth of the tree itself.<\/li>\n<\/ul>\nThe level of each node will be stored in the node content.\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">main<\/span><span style=\"color: #51afef;\">()<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #dcaeea;\">test<\/span> = add_level<span style=\"color: #c678dd;\">(<\/span><span style=\"color: #da8548; font-weight: bold;\">1<\/span>, <span style=\"color: #da8548; font-weight: bold;\">4<\/span><span style=\"color: #c678dd;\">)<\/span>;\n    <span style=\"color: #c678dd;\">println!<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #98be65;\">\"Hello, world! <\/span><span style=\"color: #98be65; font-style: italic;\">{:?}<\/span><span style=\"color: #98be65;\">\"<\/span>, test<span style=\"color: #c678dd;\">)<\/span>;\n<span style=\"color: #51afef;\">}<\/span>\n\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">add_level<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">current_level<\/span> : <span style=\"color: #ecbe7b;\">i32<\/span>, <span style=\"color: #dcaeea;\">max_level<\/span> : <span style=\"color: #ecbe7b;\">i32<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ecbe7b;\">BTree0<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">this expression is the value returned by this function<\/span>\n    <span style=\"color: #ecbe7b;\">BTree0<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #dcaeea;\">left<\/span>: <span style=\"color: #98be65;\">(<\/span>\n            <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">also if blocks can return a value<\/span>\n            <span style=\"color: #51afef;\">if<\/span> current_level &lt; max_level<span style=\"color: #a9a1e1;\">{<\/span>\n                <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">each call increases the current level until the maximum<\/span>\n                <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>add_level<span style=\"color: #98be65;\">(<\/span>current_level + <span style=\"color: #da8548; font-weight: bold;\">1<\/span>, max_level<span style=\"color: #98be65;\">)<\/span><span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>\n            <span style=\"color: #a9a1e1;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #a9a1e1;\">{<\/span>\n               <span style=\"color: #ecbe7b;\">None<\/span>\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">)<\/span>,\n        <span style=\"color: #dcaeea;\">right<\/span>: <span style=\"color: #98be65;\">(<\/span>\n            <span style=\"color: #51afef;\">if<\/span> current_level &lt; max_level<span style=\"color: #a9a1e1;\">{<\/span>\n                <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>add_level<span style=\"color: #98be65;\">(<\/span>current_level + <span style=\"color: #da8548; font-weight: bold;\">1<\/span>, max_level<span style=\"color: #98be65;\">)<\/span><span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>\n            <span style=\"color: #a9a1e1;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #a9a1e1;\">{<\/span>\n               <span style=\"color: #ecbe7b;\">None<\/span>\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">)<\/span>,\n        <span style=\"color: #dcaeea;\">content<\/span>: current_level\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nIn this code you can see an interesting idiom in Rust: each time the last eselement of a block is an expression, it is returned as a value.\n\nPlease note that these expressions are not followed by a semicolon.\n\n<\/div>\n<\/div>\n<div id=\"outline-container-org932c37e\" class=\"outline-2\">\n<h2 id=\"org932c37e\">Adding nodes to our tree<\/h2>\n<div id=\"text-org932c37e\" class=\"outline-text-2\">\n\nSome times we might want to add new branches to our tree after we built it.\n\nAn example is to create a binary tree for sorting: we first start with a single value in our root node:\n<div id=\"org1aaa23a\" class=\"figure\">\n\n<img data-recalc-dims=\"1\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/post013_rust_sort_tree_0.png?ssl=1\" alt=\"post013_rust_sort_tree_0.png\" \/>\n\n<\/div>\nas values are collected they will be eventually added to the tree: left node will have a value which is less than the parent, right node a value greater than the parent.\n<div id=\"org766f322\" class=\"figure\">\n\n<img data-recalc-dims=\"1\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/post013_rust_sort_tree_1.png?ssl=1\" alt=\"post013_rust_sort_tree_1.png\" \/>\n\n<\/div>\nThis requires quite a few Rust idioms\n<ul class=\"org-ul\">\n \t<li>we need to create a mutable root in order to send mutable references to a function, this is needed to add new branches to our initial root<\/li>\n \t<li>we need to access each node and possibly understand if it has any children: this will be done by using a pattern match on the <code>Option<\/code> enum.<\/li>\n \t<li>we need to access some children node as a mutable reference; using the <code>ref   mut<\/code> signature in the pattern match we can achieve this<\/li>\n<\/ul>\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">main<\/span><span style=\"color: #51afef;\">()<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #5b6268;\">\/\/<\/span><span style=\"color: #5b6268;\">this is the root node<\/span>\n    <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">test<\/span> = <span style=\"color: #ecbe7b;\">BTree1<\/span><span style=\"color: #c678dd;\">{<\/span> <span style=\"color: #dcaeea;\">left<\/span>: <span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">right<\/span>: <span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">content<\/span>: <span style=\"color: #da8548; font-weight: bold;\">5<\/span> <span style=\"color: #c678dd;\">}<\/span>;\n    add_element<span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> test, <span style=\"color: #da8548; font-weight: bold;\">2<\/span><span style=\"color: #c678dd;\">)<\/span>; <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">this will add a left branch<\/span>\n    add_element<span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> test, <span style=\"color: #da8548; font-weight: bold;\">4<\/span><span style=\"color: #c678dd;\">)<\/span>; <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">this will add a right branch on the left branch<\/span>\n    add_element<span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> test, <span style=\"color: #da8548; font-weight: bold;\">5<\/span><span style=\"color: #c678dd;\">)<\/span>; <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">this will be ignored<\/span>\n    add_element<span style=\"color: #c678dd;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> test, <span style=\"color: #da8548; font-weight: bold;\">6<\/span><span style=\"color: #c678dd;\">)<\/span>; <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">this will add a rigth branch<\/span>\n    <span style=\"color: #c678dd;\">println!<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #98be65;\">\"Hello, world! <\/span><span style=\"color: #98be65; font-style: italic;\">{:?}<\/span><span style=\"color: #98be65;\">\"<\/span>, test<span style=\"color: #c678dd;\">)<\/span>;\n<span style=\"color: #51afef;\">}<\/span>\n\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">add_element<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">node<\/span>: &amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #ecbe7b;\">BTree1<\/span>, <span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ecbe7b;\">i32<\/span><span style=\"color: #51afef;\">){<\/span>\n    <span style=\"color: #51afef;\">if<\/span> node.content == value<span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">if the value is already in the tree do nothing<\/span>\n        <span style=\"color: #51afef;\">return<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #51afef;\">if<\/span> node.content &lt; value <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">check the left side for smaller values<\/span>\n        <span style=\"color: #51afef;\">match<\/span> node.left <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #ecbe7b;\">None<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                node.left = <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>\n                    <span style=\"color: #ecbe7b;\">BTree1<\/span> <span style=\"color: #98be65;\">{<\/span> <span style=\"color: #dcaeea;\">left<\/span>: <span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">right<\/span> :<span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">content<\/span>: value<span style=\"color: #98be65;\">}<\/span>\n                <span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n            <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">a tricky part: we need to tell the compiler to return a<\/span>\n            <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">mutable reference from this pattern match otherwise it<\/span>\n            <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">may try to move the ownership of the data (which we don't want)<\/span>\n            <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #a9a1e1;\">)<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                add_element<span style=\"color: #51afef;\">(<\/span>subnode, value<span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">match<\/span> node.right <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #ecbe7b;\">None<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                node.right = <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>\n                    <span style=\"color: #ecbe7b;\">BTree1<\/span> <span style=\"color: #98be65;\">{<\/span> <span style=\"color: #dcaeea;\">left<\/span>: <span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">right<\/span> :<span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">content<\/span>: value<span style=\"color: #98be65;\">}<\/span>\n                <span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n            <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #a9a1e1;\">)<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                add_element<span style=\"color: #51afef;\">(<\/span>subnode, value<span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"outline-container-org3e1f1db\" class=\"outline-2\">\n<h2 id=\"org3e1f1db\">Exploring the tree<\/h2>\n<div id=\"text-org3e1f1db\" class=\"outline-text-2\">\n\nwe can extract the content of our tree in a way that shows it in order:\n<ol class=\"org-ol\">\n \t<li>enter a node<\/li>\n \t<li>if it has a left node enter the left node (back to point 1)<\/li>\n \t<li>print the content of the current node<\/li>\n \t<li>if it has a right node enter the right node (back to point 1)<\/li>\n \t<li>return to the parent node<\/li>\n<\/ol>\nthis sequence is called depth-first traversal of our binary tree.\n\nBefore implementing this you may notice that the following expression appears three times:\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #ecbe7b;\">BTree1<\/span> <span style=\"color: #51afef;\">{<\/span> <span style=\"color: #dcaeea;\">left<\/span>: <span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">right<\/span> :<span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">content<\/span>: value<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nthis creates a leaf node, i.e. a node with no children: it may deserve a function on its own:\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">make_leaf<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ecbe7b;\">i32<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ecbe7b;\">BTree1<\/span><span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #ecbe7b;\">BTree1<\/span> <span style=\"color: #c678dd;\">{<\/span> <span style=\"color: #dcaeea;\">left<\/span>: <span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">right<\/span> :<span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">content<\/span>: value<span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nthis is how the insertion code looks now using <code>make_leaf<\/code>:\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">add_element<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">node<\/span>: &amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #ecbe7b;\">BTree1<\/span>, <span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ecbe7b;\">i32<\/span><span style=\"color: #51afef;\">){<\/span>\n    <span style=\"color: #51afef;\">if<\/span> node.content == value<span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">if the value is already in the tree do nothing<\/span>\n        <span style=\"color: #51afef;\">return<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #51afef;\">if<\/span> node.content &gt; value <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">check the left side for smaller values<\/span>\n        <span style=\"color: #51afef;\">match<\/span> node.left <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #ecbe7b;\">None<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                node.left = <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>make_leaf<span style=\"color: #98be65;\">(<\/span>value<span style=\"color: #98be65;\">)<\/span><span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n            <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">a tricky part: we need to tell the compiler to return a<\/span>\n            <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">mutable reference from this pattern match otherwise it<\/span>\n            <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">may try to move the ownership of the data (which we don't want)<\/span>\n            <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #a9a1e1;\">)<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                add_element<span style=\"color: #51afef;\">(<\/span>subnode, value<span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">match<\/span> node.right <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #ecbe7b;\">None<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                node.right = <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>make_leaf<span style=\"color: #98be65;\">(<\/span>value<span style=\"color: #98be65;\">)<\/span><span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n            <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #a9a1e1;\">)<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                add_element<span style=\"color: #51afef;\">(<\/span>subnode, value<span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nnow let\u2019s implement our traversal algorithm: we are only keep exploring when children are available so, instead of a pattern matching, an <code>if let<\/code> expression is enough\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">deep_traversal_print<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #dcaeea;\">node<\/span>: &amp; <span style=\"color: #ecbe7b;\">BTree1<\/span><span style=\"color: #51afef;\">){<\/span>\n    <span style=\"color: #51afef;\">if<\/span> <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #c678dd;\">)<\/span> = node.left <span style=\"color: #c678dd;\">{<\/span>\n        deep_traversal_print<span style=\"color: #98be65;\">(<\/span>subnode<span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n    <span style=\"color: #c678dd;\">print!<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #98be65;\">\"<\/span><span style=\"color: #98be65; font-style: italic;\">{}<\/span><span style=\"color: #98be65;\"> \"<\/span>,node.content<span style=\"color: #c678dd;\">)<\/span>;\n    <span style=\"color: #51afef;\">if<\/span> <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #c678dd;\">)<\/span> = node.right <span style=\"color: #c678dd;\">{<\/span>\n        deep_traversal_print<span style=\"color: #98be65;\">(<\/span>subnode<span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nWe are all set! Also let\u2019s use a loop to create our tree\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">main<\/span><span style=\"color: #51afef;\">()<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">test<\/span> = make_leaf<span style=\"color: #c678dd;\">(<\/span><span style=\"color: #da8548; font-weight: bold;\">5<\/span><span style=\"color: #c678dd;\">)<\/span>;\n    <span style=\"color: #51afef;\">for<\/span> <span style=\"color: #dcaeea;\">i<\/span> <span style=\"color: #51afef;\">in<\/span> <span style=\"color: #c678dd;\">[<\/span><span style=\"color: #da8548; font-weight: bold;\">4<\/span>,<span style=\"color: #da8548; font-weight: bold;\">3<\/span>,<span style=\"color: #da8548; font-weight: bold;\">5<\/span>,<span style=\"color: #da8548; font-weight: bold;\">6<\/span><span style=\"color: #c678dd;\">]{<\/span>\n        add_element<span style=\"color: #98be65;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> test, i<span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n    <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">this will print 3 4 5 6<\/span>\n    deep_traversal_print<span style=\"color: #c678dd;\">(<\/span>&amp; test<span style=\"color: #c678dd;\">)<\/span>;\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"outline-container-orgae47270\" class=\"outline-2\">\n<h2 id=\"orgae47270\">Adding other Fruits<\/h2>\n<div id=\"text-orgae47270\" class=\"outline-text-2\">\n\nWhat if we want to have a tree with a different content: generics to the rescue!\n\nGenerics is the Rust way to implement \u201cparametric polymorphism\u201d, i.e. create data structures and algorithms which accept a type as a parameter.\n\nThis is how we can add a parameter <code>T<\/code> into our tree.\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef; font-weight: bold;\">#<\/span><span style=\"color: #51afef; font-weight: bold;\">[<\/span><span style=\"color: #51afef; font-weight: bold;\">derive<\/span><span style=\"color: #c678dd; font-weight: bold;\">(<\/span><span style=\"color: #51afef; font-weight: bold;\">Debug<\/span><span style=\"color: #c678dd; font-weight: bold;\">)<\/span><span style=\"color: #51afef; font-weight: bold;\">]<\/span>\n<span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #51afef;\">struct<\/span> <span style=\"color: #ecbe7b;\">BTree2<\/span><span style=\"color: #51afef;\">&lt;<\/span><span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #51afef;\">&gt;<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #dcaeea;\">left<\/span> : <span style=\"color: #ecbe7b;\">Option<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ecbe7b;\">Box<\/span><span style=\"color: #98be65;\">&lt;<\/span><span style=\"color: #ecbe7b;\">BTree2<\/span><span style=\"color: #a9a1e1;\">&lt;<\/span><span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #a9a1e1;\">&gt;<\/span><span style=\"color: #98be65;\">&gt;<\/span><span style=\"color: #c678dd;\">&gt;<\/span>,\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #dcaeea;\">right<\/span> : <span style=\"color: #ecbe7b;\">Option<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ecbe7b;\">Box<\/span><span style=\"color: #98be65;\">&lt;<\/span><span style=\"color: #ecbe7b;\">BTree2<\/span><span style=\"color: #a9a1e1;\">&lt;<\/span><span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #a9a1e1;\">&gt;<\/span><span style=\"color: #98be65;\">&gt;<\/span><span style=\"color: #c678dd;\">&gt;<\/span>,\n    <span style=\"color: #51afef;\">pub<\/span> <span style=\"color: #dcaeea;\">content<\/span> : <span style=\"color: #ecbe7b;\">T<\/span>,\n<span style=\"color: #51afef;\">}<\/span>\n\n<span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">a node can be created updating<\/span>\n<span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">the function with the generic type T<\/span>\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">make_leaf<\/span><span style=\"color: #51afef;\">&lt;<\/span><span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #51afef;\">&gt;(<\/span><span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #51afef;\">)<\/span> -&gt; <span style=\"color: #ecbe7b;\">BTree2<\/span><span style=\"color: #51afef;\">&lt;<\/span><span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #51afef;\">&gt;{<\/span>\n    <span style=\"color: #ecbe7b;\">BTree2<\/span> <span style=\"color: #c678dd;\">{<\/span> <span style=\"color: #dcaeea;\">left<\/span>: <span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">right<\/span> :<span style=\"color: #ecbe7b;\">None<\/span>, <span style=\"color: #dcaeea;\">content<\/span>: value<span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nVery nice. But what if we want to add elements and have them sorted into the tree as before?\n\nWe need to define a \u201ctotal ordering\u201d in our unknown type <code>T<\/code>; Rust defines a trait for types with a total order <code>Ord<\/code>.\n\nSo we need <code>T<\/code> to be acceptable only if it implements the <code>Ord<\/code> trait. This is called \u201cgeneric contstraint\u201d. Let\u2019s see how implement this in Rust\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">the constraint appears in the function definition<\/span>\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">add_element<\/span><span style=\"color: #51afef;\">&lt;<\/span><span style=\"color: #dcaeea;\">T<\/span>: <span style=\"color: #ecbe7b;\">Ord<\/span><span style=\"color: #51afef;\">&gt;(<\/span><span style=\"color: #dcaeea;\">node<\/span>: &amp; <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #ecbe7b;\">BTree2<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #c678dd;\">&gt;<\/span>, <span style=\"color: #dcaeea;\">value<\/span>: <span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #51afef;\">){<\/span>\n    <span style=\"color: #51afef;\">if<\/span> node.content == value<span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">return<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #51afef;\">if<\/span> node.content &gt; value <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">match<\/span> node.left <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #ecbe7b;\">None<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                node.left = <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>make_leaf<span style=\"color: #98be65;\">(<\/span>value<span style=\"color: #98be65;\">)<\/span><span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n            <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #a9a1e1;\">)<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                add_element<span style=\"color: #51afef;\">(<\/span>subnode, value<span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span> <span style=\"color: #51afef;\">else<\/span> <span style=\"color: #c678dd;\">{<\/span>\n        <span style=\"color: #51afef;\">match<\/span> node.right <span style=\"color: #98be65;\">{<\/span>\n            <span style=\"color: #ecbe7b;\">None<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                node.right = <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #51afef;\">(<\/span><span style=\"color: #ecbe7b;\">Box<\/span>::new<span style=\"color: #c678dd;\">(<\/span>make_leaf<span style=\"color: #98be65;\">(<\/span>value<span style=\"color: #98be65;\">)<\/span><span style=\"color: #c678dd;\">)<\/span><span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n            <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #a9a1e1;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #a9a1e1;\">)<\/span> =&gt; <span style=\"color: #a9a1e1;\">{<\/span>\n                add_element<span style=\"color: #51afef;\">(<\/span>subnode, value<span style=\"color: #51afef;\">)<\/span>;\n            <span style=\"color: #a9a1e1;\">}<\/span>\n        <span style=\"color: #98be65;\">}<\/span>\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nAnd what if we want to print our data when we traverse the tree? We need to implement the <code>std::fmt::Display<\/code> trait\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">use<\/span> <span style=\"color: #a9a1e1;\">std<\/span>::<span style=\"color: #a9a1e1;\">fmt<\/span>::<span style=\"color: #ecbe7b;\">Display<\/span>;\n\n<span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">deep_traversal_print<\/span><span style=\"color: #51afef;\">&lt;<\/span><span style=\"color: #dcaeea;\">T<\/span>: <span style=\"color: #ecbe7b;\">Display<\/span><span style=\"color: #51afef;\">&gt;(<\/span><span style=\"color: #dcaeea;\">node<\/span>: &amp; <span style=\"color: #ecbe7b;\">BTree2<\/span><span style=\"color: #c678dd;\">&lt;<\/span><span style=\"color: #ecbe7b;\">T<\/span><span style=\"color: #c678dd;\">&gt;<\/span><span style=\"color: #51afef;\">){<\/span>\n    <span style=\"color: #51afef;\">if<\/span> <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #c678dd;\">)<\/span> = node.left <span style=\"color: #c678dd;\">{<\/span>\n        deep_traversal_print<span style=\"color: #98be65;\">(<\/span>subnode<span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n    <span style=\"color: #c678dd;\">print!<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #98be65;\">\"<\/span><span style=\"color: #98be65; font-style: italic;\">{}<\/span><span style=\"color: #98be65;\"> \"<\/span>,node.content<span style=\"color: #c678dd;\">)<\/span>;\n    <span style=\"color: #51afef;\">if<\/span> <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #ecbe7b;\">Some<\/span><span style=\"color: #c678dd;\">(<\/span><span style=\"color: #51afef;\">ref<\/span> <span style=\"color: #dcaeea;\">subnode<\/span><span style=\"color: #c678dd;\">)<\/span> = node.right <span style=\"color: #c678dd;\">{<\/span>\n        deep_traversal_print<span style=\"color: #98be65;\">(<\/span>subnode<span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\nNow we are ready to add more fruit: let\u2019s see an example with <code>str<\/code>\n<div class=\"org-src-container\"><label class=\"org-src-name\"><\/label>\n<pre id=\"nil\" class=\"src src-rust\"><span style=\"color: #51afef;\">fn<\/span> <span style=\"color: #c678dd;\">main<\/span><span style=\"color: #51afef;\">()<\/span> <span style=\"color: #51afef;\">{<\/span>\n    <span style=\"color: #51afef;\">let<\/span> <span style=\"color: #51afef;\">mut<\/span> <span style=\"color: #dcaeea;\">test<\/span> = make_leaf<span style=\"color: #c678dd;\">(<\/span><span style=\"color: #98be65;\">\"orange\"<\/span><span style=\"color: #c678dd;\">)<\/span>;\n    <span style=\"color: #51afef;\">for<\/span> <span style=\"color: #dcaeea;\">i<\/span> <span style=\"color: #51afef;\">in<\/span> <span style=\"color: #c678dd;\">[<\/span><span style=\"color: #98be65;\">\"banana\"<\/span>,<span style=\"color: #98be65;\">\"apple\"<\/span>,<span style=\"color: #98be65;\">\"orange\"<\/span>,<span style=\"color: #98be65;\">\"mango\"<\/span><span style=\"color: #c678dd;\">]{<\/span>\n        add_element<span style=\"color: #98be65;\">(<\/span>&amp; <span style=\"color: #51afef;\">mut<\/span> test, i<span style=\"color: #98be65;\">)<\/span>;\n    <span style=\"color: #c678dd;\">}<\/span>\n    <span style=\"color: #5b6268;\">\/\/ <\/span><span style=\"color: #5b6268;\">this will print 3 4 5 6<\/span>\n    deep_traversal_print<span style=\"color: #c678dd;\">(<\/span>&amp; test<span style=\"color: #c678dd;\">)<\/span>;\n<span style=\"color: #51afef;\">}<\/span>\n<\/pre>\n<\/div>\n<\/div>\n<\/div>","protected":false},"excerpt":{"rendered":"In this post we will extend our binary tree using generics and trait constraint, and add a simple sorting algorithm based on depth first traverse.","protected":false},"author":1,"featured_media":359,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","inline_featured_image":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[5],"class_list":["post-357","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-language-learning","tag-rust"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.5 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Growing a (sorting) tree - Noise On The Net<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Growing a (sorting) tree - Noise On The Net\" \/>\n<meta property=\"og:description\" content=\"In this post we will extend our binary tree using generics and trait constraint, and add a simple sorting algorithm based on depth first traverse.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"Noise On The Net\" \/>\n<meta property=\"article:published_time\" content=\"2024-03-17T08:22:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-03-24T20:42:59+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"800\" \/>\n\t<meta property=\"og:image:height\" content=\"1200\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"marco.p.v.vezzoli\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"marco.p.v.vezzoli\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/\"},\"author\":{\"name\":\"marco.p.v.vezzoli\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\"},\"headline\":\"Growing a (sorting) tree\",\"datePublished\":\"2024-03-17T08:22:00+00:00\",\"dateModified\":\"2024-03-24T20:42:59+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/\"},\"wordCount\":661,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\"},\"image\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1\",\"keywords\":[\"Rust\"],\"articleSection\":[\"Language learning\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/\",\"url\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/\",\"name\":\"Growing a (sorting) tree - Noise On The Net\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1\",\"datePublished\":\"2024-03-17T08:22:00+00:00\",\"dateModified\":\"2024-03-24T20:42:59+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#primaryimage\",\"url\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1\",\"contentUrl\":\"https:\\\/\\\/i0.wp.com\\\/noiseonthenet.space\\\/noise\\\/wp-content\\\/uploads\\\/2024\\\/03\\\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1\",\"width\":800,\"height\":1200},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/2024\\\/03\\\/growing-a-sorting-tree\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Growing a (sorting) tree\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#website\",\"url\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/\",\"name\":\"Noise On The Net\",\"description\":\"Sharing adventures in code\",\"publisher\":{\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/#\\\/schema\\\/person\\\/88c3a70f2b23480197bc61d6e1e2e982\",\"name\":\"marco.p.v.vezzoli\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\",\"caption\":\"marco.p.v.vezzoli\"},\"logo\":{\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g\"},\"description\":\"Self taught assembler programming at 11 on my C64 (1983). Never stopped since then -- always looking up for curious things in the software development, data science and AI. Linux and FOSS user since 1994. MSc in physics in 1996. Working in large semiconductor companies since 1997 (STM, Micron) developing analytics and full stack web infrastructures, microservices, ML solutions\",\"sameAs\":[\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/\",\"https:\\\/\\\/www.linkedin.com\\\/in\\\/marco-paolo-valerio-vezzoli-0663835\\\/\"],\"url\":\"https:\\\/\\\/noiseonthenet.space\\\/noise\\\/author\\\/marco-p-v-vezzoli\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Growing a (sorting) tree - Noise On The Net","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/","og_locale":"en_US","og_type":"article","og_title":"Growing a (sorting) tree - Noise On The Net","og_description":"In this post we will extend our binary tree using generics and trait constraint, and add a simple sorting algorithm based on depth first traverse.","og_url":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/","og_site_name":"Noise On The Net","article_published_time":"2024-03-17T08:22:00+00:00","article_modified_time":"2024-03-24T20:42:59+00:00","og_image":[{"width":800,"height":1200,"url":"https:\/\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg","type":"image\/jpeg"}],"author":"marco.p.v.vezzoli","twitter_card":"summary_large_image","twitter_misc":{"Written by":"marco.p.v.vezzoli","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#article","isPartOf":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/"},"author":{"name":"marco.p.v.vezzoli","@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982"},"headline":"Growing a (sorting) tree","datePublished":"2024-03-17T08:22:00+00:00","dateModified":"2024-03-24T20:42:59+00:00","mainEntityOfPage":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/"},"wordCount":661,"commentCount":0,"publisher":{"@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982"},"image":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1","keywords":["Rust"],"articleSection":["Language learning"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/","url":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/","name":"Growing a (sorting) tree - Noise On The Net","isPartOf":{"@id":"https:\/\/noiseonthenet.space\/noise\/#website"},"primaryImageOfPage":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#primaryimage"},"image":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1","datePublished":"2024-03-17T08:22:00+00:00","dateModified":"2024-03-24T20:42:59+00:00","breadcrumb":{"@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#primaryimage","url":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1","contentUrl":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1","width":800,"height":1200},{"@type":"BreadcrumbList","@id":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-sorting-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/noiseonthenet.space\/noise\/"},{"@type":"ListItem","position":2,"name":"Growing a (sorting) tree"}]},{"@type":"WebSite","@id":"https:\/\/noiseonthenet.space\/noise\/#website","url":"https:\/\/noiseonthenet.space\/noise\/","name":"Noise On The Net","description":"Sharing adventures in code","publisher":{"@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/noiseonthenet.space\/noise\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/noiseonthenet.space\/noise\/#\/schema\/person\/88c3a70f2b23480197bc61d6e1e2e982","name":"marco.p.v.vezzoli","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g","caption":"marco.p.v.vezzoli"},"logo":{"@id":"https:\/\/secure.gravatar.com\/avatar\/b9d9aab1df560bc14d73b0b442198f196ce39e7c7a38df1dc22fec0b97f17da9?s=96&d=mm&r=g"},"description":"Self taught assembler programming at 11 on my C64 (1983). Never stopped since then -- always looking up for curious things in the software development, data science and AI. Linux and FOSS user since 1994. MSc in physics in 1996. Working in large semiconductor companies since 1997 (STM, Micron) developing analytics and full stack web infrastructures, microservices, ML solutions","sameAs":["https:\/\/noiseonthenet.space\/noise\/","https:\/\/www.linkedin.com\/in\/marco-paolo-valerio-vezzoli-0663835\/"],"url":"https:\/\/noiseonthenet.space\/noise\/author\/marco-p-v-vezzoli\/"}]}},"jetpack_featured_media_url":"https:\/\/i0.wp.com\/noiseonthenet.space\/noise\/wp-content\/uploads\/2024\/03\/jared-subia-TcDc9jLOjGU-unsplash_reduced.jpg?fit=800%2C1200&ssl=1","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pdDUZ5-5L","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts\/357","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/comments?post=357"}],"version-history":[{"count":5,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts\/357\/revisions"}],"predecessor-version":[{"id":374,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/posts\/357\/revisions\/374"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/media\/359"}],"wp:attachment":[{"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/media?parent=357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/categories?post=357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/noiseonthenet.space\/noise\/wp-json\/wp\/v2\/tags?post=357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}