{"id":19837,"date":"2023-01-18T07:25:41","date_gmt":"2023-01-18T07:25:41","guid":{"rendered":"https:\/\/www.booksofall.com\/ru\/?post_type=product&#038;p=19837"},"modified":"2023-01-18T07:25:41","modified_gmt":"2023-01-18T07:25:41","slug":"binary-trees","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/ru\/binary-trees\/","title":{"rendered":"Binary Trees"},"content":{"rendered":"<p>This article introduces the basic concepts of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Binary_tree\">binary trees<\/a>, and then works through a series of practice problems with solution code in<a href=\"https:\/\/www.naukri.com\/learning\/articles\/difference-between-c-and-cpp-programming-languages\/\"> C\/C++<\/a> and <a href=\"https:\/\/www.java.com\/en\/\">Java<\/a>. Binary trees have an elegant recursive pointer structure, so they are a good way to learn recursive pointer algorithms.<\/p>\n<h3>Contents<\/h3>\n<ul>\n<li>Section 1. Binary Tree Structure &#8212; a quick introduction to binary trees and the code that operates on them<\/li>\n<li>Section 2. Binary Tree Problems &#8212; practice problems in increasing order of difficulty<\/li>\n<li>Section 3. C Solutions &#8212; solution code to the problems for C and C++ programmers<\/li>\n<li>Section 4. Java versions &#8212; how binary trees work in Java, with solution code<\/li>\n<\/ul>\n<h3>Section 1 &#8212; Introduction To Binary Trees<\/h3>\n<p>A <a href=\"https:\/\/byjus.com\/maths\/binary-number-system\/\">binary<\/a> tree is made of nodes, where each node contains a &#8220;left&#8221; pointer, a &#8220;right&#8221; pointer, and a data element. The &#8220;root&#8221; pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller &#8220;subtrees&#8221; on either side. A null pointer represents a binary tree with no elements &#8212; the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.<\/p>\n<p>A &#8220;<a href=\"https:\/\/www.geeksforgeeks.org\/difference-between-binary-tree-and-binary-search-tree\/\">binary search tree<\/a>&#8221; (BST) or &#8220;ordered binary tree&#8221; is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (&lt;=), and all the elements in its right subtree are greater than the node (&gt;). The tree shown above is a binary search tree &#8212; the &#8220;root&#8221; node is a 5, and its left subtree nodes (1, 3, 4) are &lt;= 5, and its right subtree nodes (6, 9) are &gt; 5. Recursively, each of the subtrees must also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 &lt;= 3 and 4 &gt; 3. Watch out for the exact wording in the problems &#8212; a &#8220;binary search tree&#8221; is different from a &#8220;binary tree&#8221;.<\/p>\n<p>The nodes at the bottom edge of the tree have empty subtrees and are called &#8220;leaf&#8221; nodes (1, 4, 6) while the others are &#8220;internal&#8221; nodes (3, 5, 9).<\/p>\n<p><strong>Binary Search Tree Niche<\/strong><\/p>\n<p>Basically, binary search trees are fast at insert and lookup. The next section presents the code for these two algorithms. On average, a binary search tree algorithm can locate a node in an N node tree in order lg(N) time (log base 2). Therefore, binary search trees are good for &#8220;dictionary&#8221; problems where the code inserts and looks up information indexed by some key. The lg(N) behavior is the average case &#8212; it&#8217;s possible for a particular tree to be<br \/>\nmuch slower depending on its shape.<\/p>\n<p><strong>Strategy<\/strong><\/p>\n<p>Some of the problems in this article use plain binary trees, and some use binary search trees. In any case, the problems concentrate on the combination of pointers and recursion. (See the articles linked above for pointer articles that do not emphasize recursion.)<\/p>\n<p>For each problem, there are two things to understand&#8230;<\/p>\n<ul>\n<li>The node\/pointer structure that makes up the tree and the code that manipulates it<\/li>\n<li>The algorithm, typically recursive, that iterates over the tree<\/li>\n<\/ul>\n<p>When thinking about a binary tree problem, it&#8217;s often a good idea to draw a few little trees to think about the various cases.<\/p>\n","protected":false},"excerpt":{"rendered":"<p><iframe style=\"width: 100%; height: 750px; border: none;\" src=\"https:\/\/online.visual-paradigm.com\/share\/book\/binary-trees-185u9ryzp6?p=1\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n","protected":false},"featured_media":19840,"template":"","meta":{"_yoast_wpseo_title":"","_yoast_wpseo_metadesc":"Learn more about basic concepts of binary trees here, including their structure, problems and also the solutions, and try practicing them now!"},"product_brand":[],"product_cat":[263],"product_tag":[],"class_list":{"0":"post-19837","1":"product","2":"type-product","3":"status-publish","4":"has-post-thumbnail","6":"product_cat-algorithms-data-structures","8":"first","9":"instock","10":"shipping-taxable","11":"product-type-simple"},"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.1.1 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Binary Trees - BooksOfAll Russian<\/title>\n<meta name=\"description\" content=\"Learn more about basic concepts of binary trees here, including their structure, problems and also the solutions, and try practicing them now!\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.booksofall.com\/ru\/binary-trees\/\" \/>\n<meta property=\"og:locale\" content=\"ru_RU\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Binary Trees - BooksOfAll Russian\" \/>\n<meta property=\"og:description\" content=\"Learn more about basic concepts of binary trees here, including their structure, problems and also the solutions, and try practicing them now!\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.booksofall.com\/ru\/binary-trees\/\" \/>\n<meta property=\"og:site_name\" content=\"BooksOfAll Russian\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:image\" content=\"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg\" \/>\n<meta name=\"twitter:label1\" content=\"\u041f\u0440\u0438\u043c\u0435\u0440\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0434\u043b\u044f \u0447\u0442\u0435\u043d\u0438\u044f\" \/>\n\t<meta name=\"twitter:data1\" content=\"3 \u043c\u0438\u043d\u0443\u0442\u044b\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.booksofall.com\/ru\/binary-trees\/\",\"url\":\"https:\/\/www.booksofall.com\/ru\/binary-trees\/\",\"name\":\"Binary Trees - BooksOfAll Russian\",\"isPartOf\":{\"@id\":\"https:\/\/www.booksofall.com\/ru\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.booksofall.com\/ru\/binary-trees\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/www.booksofall.com\/ru\/binary-trees\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg\",\"datePublished\":\"2023-01-18T07:25:41+00:00\",\"description\":\"Learn more about basic concepts of binary trees here, including their structure, problems and also the solutions, and try practicing them now!\",\"breadcrumb\":{\"@id\":\"https:\/\/www.booksofall.com\/ru\/binary-trees\/#breadcrumb\"},\"inLanguage\":\"ru-RU\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.booksofall.com\/ru\/binary-trees\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"ru-RU\",\"@id\":\"https:\/\/www.booksofall.com\/ru\/binary-trees\/#primaryimage\",\"url\":\"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg\",\"contentUrl\":\"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg\",\"width\":\"827\",\"height\":\"1169\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.booksofall.com\/ru\/binary-trees\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.booksofall.com\/ru\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Categories\",\"item\":\"https:\/\/www.booksofall.com\/ru\/categories\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Binary Trees\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.booksofall.com\/ru\/#website\",\"url\":\"https:\/\/www.booksofall.com\/ru\/\",\"name\":\"BooksOfAll Russian\",\"description\":\"Biggest IT eBooks library and learning resources - Free eBooks for programming, computing, artificial intelligence and more.\",\"publisher\":{\"@id\":\"https:\/\/www.booksofall.com\/ru\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.booksofall.com\/ru\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ru-RU\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/www.booksofall.com\/ru\/#organization\",\"name\":\"BooksOfAll Russian\",\"url\":\"https:\/\/www.booksofall.com\/ru\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ru-RU\",\"@id\":\"https:\/\/www.booksofall.com\/ru\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2022\/06\/booksofall-logo-2.png\",\"contentUrl\":\"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2022\/06\/booksofall-logo-2.png\",\"width\":166,\"height\":30,\"caption\":\"BooksOfAll Russian\"},\"image\":{\"@id\":\"https:\/\/www.booksofall.com\/ru\/#\/schema\/logo\/image\/\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Binary Trees - BooksOfAll Russian","description":"Learn more about basic concepts of binary trees here, including their structure, problems and also the solutions, and try practicing them now!","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:\/\/www.booksofall.com\/ru\/binary-trees\/","og_locale":"ru_RU","og_type":"article","og_title":"Binary Trees - BooksOfAll Russian","og_description":"Learn more about basic concepts of binary trees here, including their structure, problems and also the solutions, and try practicing them now!","og_url":"https:\/\/www.booksofall.com\/ru\/binary-trees\/","og_site_name":"BooksOfAll Russian","og_image":[{"url":"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg","type":"","width":"","height":""}],"twitter_card":"summary_large_image","twitter_image":"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg","twitter_misc":{"\u041f\u0440\u0438\u043c\u0435\u0440\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0434\u043b\u044f \u0447\u0442\u0435\u043d\u0438\u044f":"3 \u043c\u0438\u043d\u0443\u0442\u044b"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.booksofall.com\/ru\/binary-trees\/","url":"https:\/\/www.booksofall.com\/ru\/binary-trees\/","name":"Binary Trees - BooksOfAll Russian","isPartOf":{"@id":"https:\/\/www.booksofall.com\/ru\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.booksofall.com\/ru\/binary-trees\/#primaryimage"},"image":{"@id":"https:\/\/www.booksofall.com\/ru\/binary-trees\/#primaryimage"},"thumbnailUrl":"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg","datePublished":"2023-01-18T07:25:41+00:00","description":"Learn more about basic concepts of binary trees here, including their structure, problems and also the solutions, and try practicing them now!","breadcrumb":{"@id":"https:\/\/www.booksofall.com\/ru\/binary-trees\/#breadcrumb"},"inLanguage":"ru-RU","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.booksofall.com\/ru\/binary-trees\/"]}]},{"@type":"ImageObject","inLanguage":"ru-RU","@id":"https:\/\/www.booksofall.com\/ru\/binary-trees\/#primaryimage","url":"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg","contentUrl":"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2023\/01\/cover-Page-10.jpg","width":"827","height":"1169"},{"@type":"BreadcrumbList","@id":"https:\/\/www.booksofall.com\/ru\/binary-trees\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.booksofall.com\/ru\/"},{"@type":"ListItem","position":2,"name":"Categories","item":"https:\/\/www.booksofall.com\/ru\/categories\/"},{"@type":"ListItem","position":3,"name":"Binary Trees"}]},{"@type":"WebSite","@id":"https:\/\/www.booksofall.com\/ru\/#website","url":"https:\/\/www.booksofall.com\/ru\/","name":"BooksOfAll Russian","description":"Biggest IT eBooks library and learning resources - Free eBooks for programming, computing, artificial intelligence and more.","publisher":{"@id":"https:\/\/www.booksofall.com\/ru\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.booksofall.com\/ru\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ru-RU"},{"@type":"Organization","@id":"https:\/\/www.booksofall.com\/ru\/#organization","name":"BooksOfAll Russian","url":"https:\/\/www.booksofall.com\/ru\/","logo":{"@type":"ImageObject","inLanguage":"ru-RU","@id":"https:\/\/www.booksofall.com\/ru\/#\/schema\/logo\/image\/","url":"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2022\/06\/booksofall-logo-2.png","contentUrl":"https:\/\/www.booksofall.com\/ru\/wp-content\/uploads\/sites\/7\/2022\/06\/booksofall-logo-2.png","width":166,"height":30,"caption":"BooksOfAll Russian"},"image":{"@id":"https:\/\/www.booksofall.com\/ru\/#\/schema\/logo\/image\/"}}]}},"_links":{"self":[{"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/product\/19837","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/product"}],"about":[{"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/types\/product"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/media\/19840"}],"wp:attachment":[{"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/media?parent=19837"}],"wp:term":[{"taxonomy":"product_brand","embeddable":true,"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/product_brand?post=19837"},{"taxonomy":"product_cat","embeddable":true,"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/product_cat?post=19837"},{"taxonomy":"product_tag","embeddable":true,"href":"https:\/\/www.booksofall.com\/ru\/wp-json\/wp\/v2\/product_tag?post=19837"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}