{"id":1108,"date":"2017-03-28T07:06:59","date_gmt":"2017-03-28T14:06:59","guid":{"rendered":"http:\/\/somethingk.com\/main\/?p=1108"},"modified":"2017-03-28T07:06:59","modified_gmt":"2017-03-28T14:06:59","slug":"binary-search-tree-traversals-in-c","status":"publish","type":"post","link":"https:\/\/somethingk.com\/main\/binary-search-tree-traversals-in-c\/","title":{"rendered":"Binary Search Tree Traversals in C++"},"content":{"rendered":"<section id=\"text-4\" class=\"widget boka-widget widget_text amr_widget\">\t\t\t<div class=\"textwidget\"><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script>\r\n<ins class=\"adsbygoogle\"\r\n     style=\"display:block; text-align:center;\"\r\n     data-ad-layout=\"in-article\"\r\n     data-ad-format=\"fluid\"\r\n     data-ad-client=\"ca-pub-7619916617995509\"\r\n     data-ad-slot=\"9102150708\"><\/ins>\r\n<script>\r\n     (adsbygoogle = window.adsbygoogle || []).push({});\r\n<\/script><\/div>\n\t\t<\/section>\n<p>So this will pretty much wrap up our short expedition into binary trees. Remember that these functions rely on my earlier posts dealing with the <a href=\"http:\/\/somethingk.com\/main\/?p=1075\">class<\/a> and <a href=\"http:\/\/somethingk.com\/main\/?p=1003\">nodes<\/a>.<\/p>\n<p>The three types of traversals we will look at are:<\/p>\n<ul>\n<li>Preorder (root, left, right)<\/li>\n<li>Inorder (left, root, right)<\/li>\n<li>Postorder (left, right, root)<\/li>\n<\/ul>\n<h4>Preorder Traversal<\/h4>\n<p>This type of traversal can be used to create duplicates of a tree and can be used to implement prefixes. Whatever order of values you put into a tree will be the order that preorder traversal gives you. So If I enter,\u00a0<strong>5 7 4 2 1 9 8 3 6\u00a0<\/strong>into a binary tree, when I use preorder traversal, I will expect to see\u00a0<strong>5 7 4 2 1 9 8 3 6.<\/strong><\/p>\n<div class=\"snippetcpt-wrap\" id=\"snippet-1109\" data-id=\"1109\" data-edit=\"\" data-copy=\"\/main\/wp-json\/wp\/v2\/posts\/1108?snippet=17b1fac833&#038;id=1109\" data-fullscreen=\"https:\/\/somethingk.com\/main\/code-snippets\/preorder-traversal-in-c\/?full-screen=1\">\n\t\t\t\t<pre class=\"prettyprint linenums lang-c_cpp\" title=\"Preorder Traversal in C++\">void preorderTraversal (Node* n) {\r\n    if (n != nullptr) { \/\/make sure we have a value\r\n        cout &lt;&lt; n-&gt;data &lt;&lt; endl; \/\/Print out the current Node value\r\n        preorderTraversal(n-&gt;left); \/\/traverse down the left side\r\n        preorderTraversal(n-&gt;right); \/\/Once we return from the left, go down the right\r\n    }\r\n}<\/pre>\n\t\t\t<\/div>\n<h4>Inorder Traversal<\/h4>\n<p>This type of traversal will return data sorted in order. So if I entered,\u00a0<strong>5 7 4 2 1 9 8 3 6<\/strong>, I would expect to see\u00a0<strong>1 2 3 4 5 6 7 8 9<\/strong>.<\/p>\n<div class=\"snippetcpt-wrap\" id=\"snippet-1110\" data-id=\"1110\" data-edit=\"\" data-copy=\"\/main\/wp-json\/wp\/v2\/posts\/1108?snippet=17b1fac833&#038;id=1110\" data-fullscreen=\"https:\/\/somethingk.com\/main\/code-snippets\/inorder-traversal-in-c\/?full-screen=1\">\n\t\t\t\t<pre class=\"prettyprint linenums lang-c_cpp\" title=\"Inorder Traversal in C++\">  void inorderTraversal (Node* n) {\r\n    if (n != nullptr) { \/\/make sure we have a value\r\n        inorderTraversal(n-&gt;left); \/\/traverse down the left side\r\n        cout &lt;&lt; n-&gt;data &lt;&lt; endl; \/\/Print out the current Node value\r\n        inorderTraversal(n-&gt;right); \/\/Once we return from the print, go down the right\r\n    }\r\n}<\/pre>\n\t\t\t<\/div>\n<h4>Postorder Traversal<\/h4>\n<p>This type of traversal can be used to implement postfixes and can cleanly be used to destroy a tree with out leaving Nodes floating around corrupting memory. So if I entered,\u00a0<strong>5 7 4 2 1 9 8 3 6<\/strong>, I would expect to see\u00a0<strong>1 3 2 4 6 8 9 7 5<\/strong><\/p>\n<div class=\"snippetcpt-wrap\" id=\"snippet-1111\" data-id=\"1111\" data-edit=\"\" data-copy=\"\/main\/wp-json\/wp\/v2\/posts\/1108?snippet=17b1fac833&#038;id=1111\" data-fullscreen=\"https:\/\/somethingk.com\/main\/code-snippets\/postorder-traversal-in-c\/?full-screen=1\">\n\t\t\t\t<pre class=\"prettyprint linenums lang-c_cpp\" title=\"Postorder Traversal in C++\"> void postorderTraversal (Node* n) {\r\n    if (n != nullptr) { \/\/make sure we have a value\r\n        postorderTraversal(n-&gt;left); \/\/traverse down the left side\r\n        postorderTraversal(n-&gt;right); \/\/Once we return from the left, go down the right\r\n        cout &lt;&lt; n-&gt;data &lt;&lt; endl; \/\/Print out the current Node value\r\n    }\r\n}<\/pre>\n\t\t\t<\/div>\n<p>For more information on binary trees, I would checkout this <a href=\"http:\/\/www.geeksforgeeks.org\/tree-traversals-inorder-preorder-and-postorder\/\">article<\/a>. It goes into detail on how traversals on called on the tree and gives some great visuals. I also liked this interactive <a href=\"https:\/\/visualgo.net\/bst\">visual<\/a> for binary search trees in general.<\/p>\n<p>Good luck!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>So this will pretty much wrap up our short expedition into binary trees. Remember that these functions rely on my earlier posts dealing with the class and nodes. The three types of traversals we will look at are: Preorder (root, left, right) Inorder (left, root, right) Postorder (left, right, root) Preorder Traversal This type of traversal can be used to [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[177],"tags":[575,539,303,579,495,580,578,510,506,577,576],"class_list":["post-1108","post","type-post","status-publish","format-standard","hentry","category-development","tag-binary","tag-bst","tag-c","tag-inorder","tag-node","tag-postorder","tag-preorder","tag-print","tag-recursion","tag-traversals","tag-tree"],"_links":{"self":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/comments?post=1108"}],"version-history":[{"count":1,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1108\/revisions"}],"predecessor-version":[{"id":1112,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1108\/revisions\/1112"}],"wp:attachment":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/media?parent=1108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/categories?post=1108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/tags?post=1108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}