{"id":413611,"date":"2024-06-29T23:14:03","date_gmt":"2024-06-29T23:14:03","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=413611"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=413611","title":{"rendered":"<span>Binary Tree<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>Data structures are classified into linear and non-linear data structures. A tree is a non-linear data structure. Data is stored hierarchically in a non-linear data structure. So the tree is a way of organizing data hierarchically. A tree grows from top to bottom. In a tree, there are different kinds of nodes that are linked with each other. A tree consists of the following elements:<\/p>\n<ul>\n<li>\n<p>Node: It is an element of a tree.<\/p>\n<\/li>\n<li>\n<p>Root: It is the starting node of a tree. It is the top most element that has no parent element.<\/p>\n<\/li>\n<li>\n<p>Parent Node: It is the node that has branches from top to bottom. It is the immediate predecessor of any node.<\/p>\n<\/li>\n<li>\n<p>Child Node: It is the node that has a node from bottom to top. It is the instantaneous successor of any node.<\/p>\n<\/li>\n<li>\n<p>Level: Each step in a tree is level.<\/p>\n<\/li>\n<li>\n<p>Leaf Node: It is the node having no child.<\/p>\n<\/li>\n<li>\n<p>Non-Leaf Node: It is the node having at least one child.<\/p>\n<\/li>\n<li>\n<p>Edge: It is the link between two nodes.<\/p>\n<\/li>\n<li>\n<p>Sibling: It is the child node with the same parents.<\/p>\n<\/li>\n<li>\n<p>Internal Nodes: These are the nodes that have child nodes.<\/p>\n<\/li>\n<li>\n<p>Degree: It is the largest number of child nodes.<\/p>\n<\/li>\n<li>\n<p>Path: It is a sequence of nodes along with the boundaries of a tree.<\/p>\n<\/li>\n<\/ul>\n<p>In a binary tree,\u00a0 every node in a tree should have a maximum of two children. It means that a tree can constitute either 0, 1, or 2 nodes. Let\u2019s consider a tree shown below. In this figure, node \u2018a\u2019 has two children(b and f). Similarly, node b has also two children (d and e) and the same for node f.\u00a0 And node \u2018f \u2019 has also two children (g and h) Each node has a maximum of two children. A binary tree usually consists of three nodes:<\/p>\n<ul>\n<li>\n<p>Root Node<\/p>\n<\/li>\n<li>\n<p>Internal Node<\/p>\n<\/li>\n<li>\n<p>Leaf Node<\/p>\n<\/li>\n<\/ul>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/9a8\/67e\/63f\/9a867e63f9a4d2739265f1ec2877f4a0.png\" width=\"433\" height=\"205\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9a8\/67e\/63f\/9a867e63f9a4d2739265f1ec2877f4a0.png\"\/><figcaption><\/figcaption><\/figure>\n<h2>Types of Binary Tree<\/h2>\n<p>It has been classified into the following different categories:<\/p>\n<ul>\n<li>\n<p>Full Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Perfect Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Almost Complete Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Complete Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Left Skewed Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Right Skewed Binary Tree<\/p>\n<\/li>\n<li>\n<p>Balanced Binary Tree<\/p>\n<\/li>\n<\/ul>\n<h2>1. Full Binary Tree<\/h2>\n<p>It is also known as a strictly or proper binary tree. In this, every single node has two or zero children excluding the leaf nodes. Let us consider the following example, in which we have parent nodes (a,b,c,d) and leaf nodes(e,f,g,h,k). Each of the parent nodes has exactly two or zero children but leaf nodes have no children.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/524\/4e0\/87b\/5244e087be742248a153dafd9f06029c.png\" width=\"399\" height=\"272\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/524\/4e0\/87b\/5244e087be742248a153dafd9f06029c.png\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Properties of Full Binary Tree  <\/strong><\/p>\n<p>It has the following properties:<\/p>\n<ol>\n<li>\n<p>It has the following maximum range of nodes :<\/p>\n<\/li>\n<\/ol>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/a61\/682\/8c4\/a616828c46596e9feb1b640237532a1d.png\" width=\"883\" height=\"40\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a61\/682\/8c4\/a616828c46596e9feb1b640237532a1d.png\"\/><figcaption><\/figcaption><\/figure>\n<p>And x= height of the full binary tree   <\/p>\n<p>    2. Its minimum range of nodes\u00a0 is:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"     2x+1\" alt=\"     2x+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/da2\/09a\/4b1\/da209a4b1808230657b6b1a1a87aedf0.svg\" width=\"45\" height=\"15\"\/><\/p>\n<p>    3. Its maximum height for <em>&#8216;n&#8217; <\/em>nodes is:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(n-1)\/2\" alt=\"(n-1)\/2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d4b\/159\/785\/d4b159785eb7461dc5d0b488932747c6.svg\" width=\"67\" height=\"20\"\/><\/p>\n<p>    4. Its minimum height for <em>&#8216;n&#8217;<\/em> nodes is:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/37c\/4a5\/fd8\/37c4a5fd879f06aeb20bc0d98215f8c7.png\" width=\"878\" height=\"43\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/37c\/4a5\/fd8\/37c4a5fd879f06aeb20bc0d98215f8c7.png\"\/><figcaption><\/figcaption><\/figure>\n<p>    5. The range of leaf nodes for <em>&#8216;n&#8217; <\/em>internal nodes is :  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"       n+1\" alt=\"       n+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ede\/660\/4bf\/ede6604bf4627275ad3e333b4c2b42f7.svg\" width=\"38\" height=\"15\"\/><\/p>\n<h3>2. Perfect Binary Tree<\/h3>\n<p>In this type, all the internal nodes must have two children and the entire leaf nodes are at a similar level. This can be a full and complete binary tree as well.<\/p>\n<p>To understand, let us consider an example shown below. This binary tree consists of three levels: internal nodes contain two child each and leaf nodes are also at an equal level.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/750\/e0d\/4ac\/750e0d4acdc9d6f22b070c96bc34137f.png\" width=\"630\" height=\"300\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/750\/e0d\/4ac\/750e0d4acdc9d6f22b070c96bc34137f.png\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Properties of Perfect Binary Tree  <\/strong><\/p>\n<p>It\u00a0 has the following properties:  <\/p>\n<ol>\n<li>\n<p>The\u00a0 leaf nodes for &#8216;x&#8217; height in it are:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/e7e\/73a\/90e\/e7e73a90e69a0a7bea799529f4bb3ecc.png\" width=\"953\" height=\"32\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e7e\/73a\/90e\/e7e73a90e69a0a7bea799529f4bb3ecc.png\"\/><figcaption><\/figcaption><\/figure>\n<\/li>\n<\/ol>\n<p>    2. The range of internal nodes in it is:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/5e5\/7b7\/da0\/5e57b7da0d17c8d35e9c5de2d30f30fa.png\" width=\"966\" height=\"45\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5e5\/7b7\/da0\/5e57b7da0d17c8d35e9c5de2d30f30fa.png\"\/><figcaption><\/figcaption><\/figure>\n<p>And x= height of the tree.  <\/p>\n<p>    3. The maximum range of nodes in it is:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/6d7\/16d\/7a6\/6d716d7a60d1754e31b3ba7a4be4ff6b.png\" width=\"972\" height=\"33\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6d7\/16d\/7a6\/6d716d7a60d1754e31b3ba7a4be4ff6b.png\"\/><figcaption><\/figcaption><\/figure>\n<p>    4. The minimum range of nodes in it is:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"  x+1\" alt=\"  x+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/845\/6fa\/875\/8456fa875177ab86c33bcf1ea3893ad2.svg\" width=\"37\" height=\"15\"\/><\/p>\n<h2>3. Almost Complete Binary Tree  <\/h2>\n<p>It is also named an \u201cincomplete binary tree\u201d. In this sort of binary tree, every single node must have two children in all levels apart from the last level but the first left child should be filled and then the right one.<\/p>\n<p>Let us consider an example below. In this , there are a total five levels(0,1,2,3,4). In level 1, there are a total of 2 nodes in which each of the nodes has two children. Similarly, level 2 has 4 and level 3 has 8 nodes with their corresponding two children. Then we have two leaf nodes x and y at the end which are filled from left to right. <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/3a1\/2ce\/af1\/3a12ceaf12218f1ca62a033613ecf91a.png\" width=\"682\" height=\"355\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3a1\/2ce\/af1\/3a12ceaf12218f1ca62a033613ecf91a.png\"\/><figcaption><\/figcaption><\/figure>\n<h2>4. Complete Binary Tree  <\/h2>\n<p>This is also called the \u201cperfect binary tree\u201d. In this, all levels are completely filled. And every node in each level must have two children and each level must comprising of 2N nodes. Where \u2018N\u2019 is the level number. And the last level has nodes as left as possible.<\/p>\n<p>Let\u2019s consider the following example. There are total four levels (0,1,2,3). Each level has the range of nodes in the following sequence:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/cf8\/802\/f12\/cf8802f1251e007b2c07cf0ad76c6c4d.png\" width=\"989\" height=\"192\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cf8\/802\/f12\/cf8802f1251e007b2c07cf0ad76c6c4d.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/d61\/f9b\/3eb\/d61f9b3eb8178282662ea2d2ddc5cf2f.png\" width=\"641\" height=\"316\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d61\/f9b\/3eb\/d61f9b3eb8178282662ea2d2ddc5cf2f.png\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Properties of Complete Binary Tree<\/strong>  <\/p>\n<p>It has the following properties:  <\/p>\n<ol>\n<li>\n<p>The maximum range of nodes in it are:  <\/p>\n<\/li>\n<\/ol>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/1ea\/ba3\/8fa\/1eaba38fa599ce68be15fd9d388c751f.png\" width=\"996\" height=\"33\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ea\/ba3\/8fa\/1eaba38fa599ce68be15fd9d388c751f.png\"\/><figcaption><\/figcaption><\/figure>\n<p>And x=\u00a0 Tree height.   <\/p>\n<p>    2. The minimum range of nodes in it are:     <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/f1d\/9e5\/c6d\/f1d9e5c6d0d82a84c0aed421fceda4df.png\" width=\"1018\" height=\"34\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f1d\/9e5\/c6d\/f1d9e5c6d0d82a84c0aed421fceda4df.png\"\/><figcaption><\/figcaption><\/figure>\n<p>     3. Its maximum height for <em>&#8216;n&#8217;<\/em> number of nodes is:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ea5\/40e\/303\/ea540e3033c0057fc95494562435fb0d.png\" width=\"1017\" height=\"32\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ea5\/40e\/303\/ea540e3033c0057fc95494562435fb0d.png\"\/><figcaption><\/figcaption><\/figure>\n<p>      4. Its minimum height for <em>&#8216;n&#8217;<\/em> number of nodes is:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/513\/f9f\/ae5\/513f9fae563b8a282ada37305ca2fcd5.png\" width=\"994\" height=\"40\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/513\/f9f\/ae5\/513f9fae563b8a282ada37305ca2fcd5.png\"\/><figcaption><\/figcaption><\/figure>\n<h2>5. Left Skewed Binary Tree <\/h2>\n<p>It consists of nodes consisting of only left children. It has only left subtree or only left children. It is the left side-dominated tree. All the right side children remain null.<\/p>\n<p>Let us consider an example as shown below. In this, the root node is \u2018a\u2019 and the leaf node is \u2018d\u2019. While internal nodes are \u2018b\u2019 and \u2018d\u2019. <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/123\/4c4\/5af\/1234c45af1979e962c93b85aca869282.png\" width=\"197\" height=\"247\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/123\/4c4\/5af\/1234c45af1979e962c93b85aca869282.png\"\/><figcaption><\/figcaption><\/figure>\n<h2>6. Right Skewed Binary Tree  <\/h2>\n<p>In this type of binary tree, there exist nodes consisting of only the right children. It is vice versa of the left-skewed binary tree. It is a right-side-dominated tree. It contains no left child.\u00a0<\/p>\n<p>Following is the example of a right-skewed binary tree. \u2018a\u2019 and \u2018b\u2019 are root and leaf nodes while \u2018b\u2019 and \u2018c\u2019 are internal nodes.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/c9b\/722\/260\/c9b722260edc0e7e78d083b65a0c2fee.png\" width=\"235\" height=\"222\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c9b\/722\/260\/c9b722260edc0e7e78d083b65a0c2fee.png\"\/><figcaption><\/figcaption><\/figure>\n<h3>7. Balanced Binary Tree    <\/h3>\n<p>In this, the height of the left subtree and right subtree of every single node might vary by one.<\/p>\n<p>Let&#8217;s consider the following example. As it can be seen, the height of the left subtree is three. And the height of the right subtree is two. So their height difference will be 1. Hence it is a balanced binary tree.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/42c\/4a5\/7cb\/42c4a57cb565a1308563220ef80c09d8.png\" width=\"209\" height=\"227\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/42c\/4a5\/7cb\/42c4a57cb565a1308563220ef80c09d8.png\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Binary Tree Representation<\/strong>  <\/p>\n<p>A binary tree can be represented by two methods.<\/p>\n<ul>\n<li>\n<p>Using Array Method<\/p>\n<\/li>\n<li>\n<p>Using the Linked List Method<\/p>\n<\/li>\n<\/ul>\n<h2>1. Array Method  <\/h2>\n<p>In this method, a binary tree is represented using a single-dimensional array. So for this purpose, the root node will be considered at zero index position. Based on the position of the parent, the left and right child will be calculated. So, the left child will be placed at <em>&#8216;2n+1&#8217;<\/em> and the right child will place at <em>&#8216;2n+2&#8217;<\/em>. Here n is the position of parent.  <\/p>\n<p><strong>Example<\/strong> <strong> <\/strong><\/p>\n<p>Let us consider the following example of the array method in which a binary tree has been taken as shown below which will be stored in a one-dimensional array. In this tree, \u2018a\u2019 is the root node. Node \u2019b\u2019 has two children \u2018d\u2019 and \u2018e\u2019. While nodes \u2018d\u2019 and \u2018e\u2019 has one left node each.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/f54\/930\/eb1\/f54930eb14026e63a18147960b3bfecf.png\" width=\"319\" height=\"282\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f54\/930\/eb1\/f54930eb14026e63a18147960b3bfecf.png\"\/><figcaption><\/figcaption><\/figure>\n<p>In this tree, \u2018a\u2019 is the root node so it will be placed at zero index in an array.\u00a0<\/p>\n<p>For the index position of left child \u2018b\u2019 :<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"20+1=1 \" alt=\"20+1=1 \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/05f\/b80\/2c9\/05fb802c93b52a8884bcde4692e2e6f0.svg\" width=\"74\" height=\"15\"\/><\/p>\n<p>\u00a0For the index location of the right child \u2018c\u2019:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"20+2=2\" alt=\"20+2=2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9e8\/588\/270\/9e8588270a2cbde22f37b763423f56e1.svg\" width=\"74\" height=\"15\"\/><\/p>\n<p>For the index location of the left child of \u2018d\u2019:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"   21+1=3    \" alt=\"   21+1=3    \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/196\/e68\/3b5\/196e683b56e59d04447020a8d0ee733b.svg\" width=\"74\" height=\"15\"\/><\/p>\n<p>For the index location of the right child of \u2018e\u2019:   <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"  21+2=4\" alt=\"  21+2=4\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4c8\/369\/b0e\/4c8369b0ef2de9e048eba2c0be8c2f91.svg\" width=\"74\" height=\"16\"\/><\/p>\n<p>For the index location of the left child of \u2018f\u2019:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"   23+1=7   \" alt=\"   23+1=7   \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/46e\/03e\/191\/46e03e191817bc949bf24c625d679c66.svg\" width=\"74\" height=\"16\"\/><\/p>\n<p>\u00a0For the index location of the left child of \u2018g\u2019:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\" 24+1=9    \" alt=\" 24+1=9    \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1d1\/cae\/db2\/1d1caedb20ce3b83ae94bb36ed29f34e.svg\" width=\"74\" height=\"16\"\/><\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/c7d\/43e\/e97\/c7d43ee97f925f030ccd431d939b7b7a.png\" width=\"805\" height=\"89\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c7d\/43e\/e97\/c7d43ee97f925f030ccd431d939b7b7a.png\"\/><figcaption><\/figcaption><\/figure>\n<h2>2. Linked List\u00a0 Method  <\/h2>\n<p>In this, a double-linked list will be used to represent every single node of the binary tree. In a doubly-linked list, there will be three fields i.e. address of the left child, root and address of right child fields.  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/26c\/b3d\/a63\/26cb3da63d69dc4fb95a9048ccd43c50.png\" width=\"870\" height=\"104\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/26c\/b3d\/a63\/26cb3da63d69dc4fb95a9048ccd43c50.png\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Example  <\/strong><\/p>\n<p>Let us consider an example in which a binary tree has been taken with two children on each node. \u2019a\u2019 is the root node in this tree. Every node has a left and right pointer. The left pointer will point towards the left child of the node and the right pointer will point towards the right node. The left and child addresses for leaf nodes will be assigned as <em>\u2018Null Address\u2019<\/em>.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/3ae\/6ec\/a8e\/3ae6eca8e8612d01221f205acb31a0e1.png\" width=\"363\" height=\"216\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3ae\/6ec\/a8e\/3ae6eca8e8612d01221f205acb31a0e1.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/00f\/c54\/789\/00fc54789633b7222de34a79bb3c7713.png\" width=\"965\" height=\"334\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/00f\/c54\/789\/00fc54789633b7222de34a79bb3c7713.png\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Binary Tree Traversals <\/strong> <\/p>\n<p>A binary tree consists of different nodes. So there are three methods to traverse a tree:<\/p>\n<ul>\n<li>\n<p>Inorder Traversal<\/p>\n<\/li>\n<li>\n<p>Preorder Traversal<\/p>\n<\/li>\n<li>\n<p>Postorder Traversal<\/p>\n<\/li>\n<\/ul>\n<h2>1. Inorder Traversal  <\/h2>\n<p>Inorder traversal means that the left child comes first in the order then the root node and right child will come. It has the following traversal order:<\/p>\n<p><em>Left Child >> Root Node >> Right Child<\/em><\/p>\n<p>To understand this, let us consider the following tree:<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/cb7\/97a\/07f\/cb797a07f39222ccdc795ca8b4d82ae0.png\" width=\"260\" height=\"141\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cb7\/97a\/07f\/cb797a07f39222ccdc795ca8b4d82ae0.png\"\/><figcaption><\/figcaption><\/figure>\n<p>In the above tree, a root node is \u2018a\u2019 while left and right nodes are \u2018b\u2019 and \u2018c\u2019.Its inorder traversal will be:  <\/p>\n<p><img class=\"formula\" source=\"  b  >> a  >> c&#187; alt=&#187;  b  >> a  >> c&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/443\/7e5\/c13\/4437e5c1383717e6437acac0f25689b0.svg&#187; width=&#187;91&#8243; height=&#187;15&#8243;\/><\/p>\n<h3>2. Preorder Traversal <\/h3>\n<p>Preorder traversal means that the root node comes first in the order then left child and right child will come. It has the following traversal order:<\/p>\n<p><em>Root Node >> Left Child >> Right Child<\/em><\/p>\n<p>To understand its concept, we will consider the above binary tree. Its preorder traversal will be:<\/p>\n<p><img class=\"formula\" source=\"      a  >> b  >> c&#187; alt=&#187;      a  >> b  >> c&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5b9\/f18\/fbe\/5b9f18fbedfc8d93998ebc8e355c38bd.svg&#187; width=&#187;91&#8243; height=&#187;15&#8243;\/><\/p>\n<h2>3. Postorder Traversal  <\/h2>\n<p>Postorder traversal means that the left child comes first in the order then the right child and root node will come. It has the following traversal order:  <\/p>\n<p><em>Left Child >> Right Child >> Root Node  <\/em><\/p>\n<p>To understand its concept, we will consider the previous binary tree. Its postorder traversal will be:  <\/p>\n<p><img class=\"formula\" source=\" b  >> c  >> a&#187; alt=&#187; b  >> c  >> a&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a5f\/bc0\/1fa\/a5fbc01fa3782bbd9b5f8e7267e176d6.svg&#187; width=&#187;91&#8243; height=&#187;15&#8243;\/><\/p>\n<p><strong>Example <\/strong> <\/p>\n<p>To understand the concept of binary tree traversals, let us consider the following binary tree. It has an \u20181\u2019 root node.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/238\/558\/1ab\/2385581ab94fe563939f96fbb01560f1.png\" width=\"464\" height=\"282\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/238\/558\/1ab\/2385581ab94fe563939f96fbb01560f1.png\"\/><figcaption><\/figcaption><\/figure>\n<p>For inorder traversal , we have:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\" 3 2 1 5 7 4 8 6 9\" alt=\" 3 2 1 5 7 4 8 6 9\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9b1\/0d2\/d98\/9b10d2d98e892ecfa618245eadfd50ca.svg\" width=\"73\" height=\"15\"\/><\/p>\n<p>For preorder traversal, we have:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"1 2 3 4 3 5 7 6 8 9\" alt=\"1 2 3 4 3 5 7 6 8 9\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d52\/9eb\/704\/d529eb704ddc1ba878e8c7128c3c3b05.svg\" width=\"81\" height=\"15\"\/><\/p>\n<p>For postorder traversal, we have:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\" 3 2 7 5 8 9 6 4 1\" alt=\" 3 2 7 5 8 9 6 4 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/de2\/e2a\/fb8\/de2e2afb88a41025e537303c820f1b93.svg\" width=\"73\" height=\"15\"\/><\/p>\n<p><strong>Properties of Binary Tree  <\/strong><\/p>\n<p>It has the following properties:  <\/p>\n<ol>\n<li>\n<p>The maximum range of nodes in it is:  <\/p>\n<\/li>\n<\/ol>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/841\/b50\/a17\/841b50a172bbfd6a15c81cb52b5be4aa.png\" width=\"850\" height=\"34\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/841\/b50\/a17\/841b50a172bbfd6a15c81cb52b5be4aa.png\"\/><figcaption><\/figcaption><\/figure>\n<p>And x= Tree height\u00a0   <\/p>\n<p>    2. The minimum range of nodes in it is:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x+1\" alt=\"x+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3fa\/ade\/703\/3faade7039dd517a1bc9436a028316b9.svg\" width=\"37\" height=\"15\"\/><\/p>\n<p>    3. Its maximum height for <em>&#8216;n&#8217;<\/em> number of nodes is:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"n-1\" alt=\"n-1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/330\/df8\/230\/330df823054ec51a078618fd6724b02e.svg\" width=\"38\" height=\"15\"\/><\/p>\n<p>    4. Its maximum height tree for<em> &#8216;n&#8217; <\/em>number of nodes is:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/0e1\/785\/19f\/0e178519fa9835d97a1a4dfb953fc878.png\" width=\"980\" height=\"46\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0e1\/785\/19f\/0e178519fa9835d97a1a4dfb953fc878.png\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Application of Binary Tree  <\/strong><\/p>\n<p>It has the following applications:<\/p>\n<ul>\n<li>\n<p>It is used to find duplicate nodes.<\/p>\n<\/li>\n<li>\n<p>It is also used in sorting and in the traversal.<\/p>\n<\/li>\n<li>\n<p>Its practical application is in an organization where binary trees are used to organize data in a sequence.<\/p>\n<\/li>\n<li>\n<p>It is also used in machine learning, database tables, encryption and routing.<\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/560060\/\"> https:\/\/habr.com\/ru\/articles\/560060\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>Data structures are classified into linear and non-linear data structures. A tree is a non-linear data structure. Data is stored hierarchically in a non-linear data structure. So the tree is a way of organizing data hierarchically. A tree grows from top to bottom. In a tree, there are different kinds of nodes that are linked with each other. A tree consists of the following elements:<\/p>\n<ul>\n<li>\n<p>Node: It is an element of a tree.<\/p>\n<\/li>\n<li>\n<p>Root: It is the starting node of a tree. It is the top most element that has no parent element.<\/p>\n<\/li>\n<li>\n<p>Parent Node: It is the node that has branches from top to bottom. It is the immediate predecessor of any node.<\/p>\n<\/li>\n<li>\n<p>Child Node: It is the node that has a node from bottom to top. It is the instantaneous successor of any node.<\/p>\n<\/li>\n<li>\n<p>Level: Each step in a tree is level.<\/p>\n<\/li>\n<li>\n<p>Leaf Node: It is the node having no child.<\/p>\n<\/li>\n<li>\n<p>Non-Leaf Node: It is the node having at least one child.<\/p>\n<\/li>\n<li>\n<p>Edge: It is the link between two nodes.<\/p>\n<\/li>\n<li>\n<p>Sibling: It is the child node with the same parents.<\/p>\n<\/li>\n<li>\n<p>Internal Nodes: These are the nodes that have child nodes.<\/p>\n<\/li>\n<li>\n<p>Degree: It is the largest number of child nodes.<\/p>\n<\/li>\n<li>\n<p>Path: It is a sequence of nodes along with the boundaries of a tree.<\/p>\n<\/li>\n<\/ul>\n<p>In a binary tree,\u00a0 every node in a tree should have a maximum of two children. It means that a tree can constitute either 0, 1, or 2 nodes. Let\u2019s consider a tree shown below. In this figure, node \u2018a\u2019 has two children(b and f). Similarly, node b has also two children (d and e) and the same for node f.\u00a0 And node \u2018f \u2019 has also two children (g and h) Each node has a maximum of two children. A binary tree usually consists of three nodes:<\/p>\n<ul>\n<li>\n<p>Root Node<\/p>\n<\/li>\n<li>\n<p>Internal Node<\/p>\n<\/li>\n<li>\n<p>Leaf Node<\/p>\n<\/li>\n<\/ul>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<h2>Types of Binary Tree<\/h2>\n<p>It has been classified into the following different categories:<\/p>\n<ul>\n<li>\n<p>Full Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Perfect Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Almost Complete Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Complete Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Left Skewed Binary Tree.<\/p>\n<\/li>\n<li>\n<p>Right Skewed Binary Tree<\/p>\n<\/li>\n<li>\n<p>Balanced Binary Tree<\/p>\n<\/li>\n<\/ul>\n<h2>1. Full Binary Tree<\/h2>\n<p>It is also known as a strictly or proper binary tree. In this, every single node has two or zero children excluding the leaf nodes. Let us consider the following example, in which we have parent nodes (a,b,c,d) and leaf nodes(e,f,g,h,k). Each of the parent nodes has exactly two or zero children but leaf nodes have no children.<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p><strong>Properties of Full Binary Tree  <\/strong><\/p>\n<p>It has the following properties:<\/p>\n<ol>\n<li>\n<p>It has the following maximum range of nodes :<\/p>\n<\/li>\n<\/ol>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>And x= height of the full binary tree   <\/p>\n<p>    2. Its minimum range of nodes\u00a0 is:  <\/p>\n<p>    3. Its maximum height for <em>&#8216;n&#8217; <\/em>nodes is:  <\/p>\n<p>    4. Its minimum height for <em>&#8216;n&#8217;<\/em> nodes is:  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>    5. The range of leaf nodes for <em>&#8216;n&#8217; <\/em>internal nodes is :  <\/p>\n<h3>2. Perfect Binary Tree<\/h3>\n<p>In this type, all the internal nodes must have two children and the entire leaf nodes are at a similar level. This can be a full and complete binary tree as well.<\/p>\n<p>To understand, let us consider an example shown below. This binary tree consists of three levels: internal nodes contain two child each and leaf nodes are also at an equal level.<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p><strong>Properties of Perfect Binary Tree  <\/strong><\/p>\n<p>It\u00a0 has the following properties:  <\/p>\n<ol>\n<li>\n<p>The\u00a0 leaf nodes for &#8216;x&#8217; height in it are:  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<\/li>\n<\/ol>\n<p>    2. The range of internal nodes in it is:  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>And x= height of the tree.  <\/p>\n<p>    3. The maximum range of nodes in it is:<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>    4. The minimum range of nodes in it is:  <\/p>\n<h2>3. Almost Complete Binary Tree  <\/h2>\n<p>It is also named an \u201cincomplete binary tree\u201d. In this sort of binary tree, every single node must have two children in all levels apart from the last level but the first left child should be filled and then the right one.<\/p>\n<p>Let us consider an example below. In this , there are a total five levels(0,1,2,3,4). In level 1, there are a total of 2 nodes in which each of the nodes has two children. Similarly, level 2 has 4 and level 3 has 8 nodes with their corresponding two children. Then we have two leaf nodes x and y at the end which are filled from left to right. <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<h2>4. Complete Binary Tree  <\/h2>\n<p>This is also called the \u201cperfect binary tree\u201d. In this, all levels are completely filled. And every node in each level must have two children and each level must comprising of 2N nodes. Where \u2018N\u2019 is the level number. And the last level has nodes as left as possible.<\/p>\n<p>Let\u2019s consider the following example. There are total four levels (0,1,2,3). Each level has the range of nodes in the following sequence:<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p><strong>Properties of Complete Binary Tree<\/strong>  <\/p>\n<p>It has the following properties:  <\/p>\n<ol>\n<li>\n<p>The maximum range of nodes in it are:  <\/p>\n<\/li>\n<\/ol>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>And x=\u00a0 Tree height.   <\/p>\n<p>    2. The minimum range of nodes in it are:     <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>     3. Its maximum height for <em>&#8216;n&#8217;<\/em> number of nodes is:  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>      4. Its minimum height for <em>&#8216;n&#8217;<\/em> number of nodes is:  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<h2>5. Left Skewed Binary Tree <\/h2>\n<p>It consists of nodes consisting of only left children. It has only left subtree or only left children. It is the left side-dominated tree. All the right side children remain null.<\/p>\n<p>Let us consider an example as shown below. In this, the root node is \u2018a\u2019 and the leaf node is \u2018d\u2019. While internal nodes are \u2018b\u2019 and \u2018d\u2019. <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<h2>6. Right Skewed Binary Tree  <\/h2>\n<p>In this type of binary tree, there exist nodes consisting of only the right children. It is vice versa of the left-skewed binary tree. It is a right-side-dominated tree. It contains no left child.\u00a0<\/p>\n<p>Following is the example of a right-skewed binary tree. \u2018a\u2019 and \u2018b\u2019 are root and leaf nodes while \u2018b\u2019 and \u2018c\u2019 are internal nodes.<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<h3>7. Balanced Binary Tree    <\/h3>\n<p>In this, the height of the left subtree and right subtree of every single node might vary by one.<\/p>\n<p>Let&#8217;s consider the following example. As it can be seen, the height of the left subtree is three. And the height of the right subtree is two. So their height difference will be 1. Hence it is a balanced binary tree.<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p><strong>Binary Tree Representation<\/strong>  <\/p>\n<p>A binary tree can be represented by two methods.<\/p>\n<ul>\n<li>\n<p>Using Array Method<\/p>\n<\/li>\n<li>\n<p>Using the Linked List Method<\/p>\n<\/li>\n<\/ul>\n<h2>1. Array Method  <\/h2>\n<p>In this method, a binary tree is represented using a single-dimensional array. So for this purpose, the root node will be considered at zero index position. Based on the position of the parent, the left and right child will be calculated. So, the left child will be placed at <em>&#8216;2n+1&#8217;<\/em> and the right child will place at <em>&#8216;2n+2&#8217;<\/em>. Here n is the position of parent.  <\/p>\n<p><strong>Example<\/strong> <strong> <\/strong><\/p>\n<p>Let us consider the following example of the array method in which a binary tree has been taken as shown below which will be stored in a one-dimensional array. In this tree, \u2018a\u2019 is the root node. Node \u2019b\u2019 has two children \u2018d\u2019 and \u2018e\u2019. While nodes \u2018d\u2019 and \u2018e\u2019 has one left node each.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>In this tree, \u2018a\u2019 is the root node so it will be placed at zero index in an array.\u00a0<\/p>\n<p>For the index position of left child \u2018b\u2019 :<\/p>\n<p>\u00a0For the index location of the right child \u2018c\u2019:  <\/p>\n<p>For the index location of the left child of \u2018d\u2019:  <\/p>\n<p>For the index location of the right child of \u2018e\u2019:   <\/p>\n<p>For the index location of the left child of \u2018f\u2019:  <\/p>\n<p>\u00a0For the index location of the left child of \u2018g\u2019:  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<h2>2. Linked List\u00a0 Method  <\/h2>\n<p>In this, a double-linked list will be used to represent every single node of the binary tree. In a doubly-linked list, there will be three fields i.e. address of the left child, root and address of right child fields.  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p><strong>Example  <\/strong><\/p>\n<p>Let us consider an example in which a binary tree has been taken with two children on each node. \u2019a\u2019 is the root node in this tree. Every node has a left and right pointer. The left pointer will point towards the left child of the node and the right pointer will point towards the right node. The left and child addresses for leaf nodes will be assigned as <em>\u2018Null Address\u2019<\/em>.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p><strong>Binary Tree Traversals <\/strong> <\/p>\n<p>A binary tree consists of different nodes. So there are three methods to traverse a tree:<\/p>\n<ul>\n<li>\n<p>Inorder Traversal<\/p>\n<\/li>\n<li>\n<p>Preorder Traversal<\/p>\n<\/li>\n<li>\n<p>Postorder Traversal<\/p>\n<\/li>\n<\/ul>\n<h2>1. Inorder Traversal  <\/h2>\n<p>Inorder traversal means that the left child comes first in the order then the root node and right child will come. It has the following traversal order:<\/p>\n<p><em>Left Child >> Root Node >> Right Child<\/em><\/p>\n<p>To understand this, let us consider the following tree:<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>In the above tree, a root node is \u2018a\u2019 while left and right nodes are \u2018b\u2019 and \u2018c\u2019.Its inorder traversal will be:  <\/p>\n<p>> a  >> c&#187; alt=&#187;  b  >> a  >> c&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/443\/7e5\/c13\/4437e5c1383717e6437acac0f25689b0.svg&#187; width=&#187;91&#8243; height=&#187;15&#8243;\/><\/p>\n<h3>2. Preorder Traversal <\/h3>\n<p>Preorder traversal means that the root node comes first in the order then left child and right child will come. It has the following traversal order:<\/p>\n<p><em>Root Node >> Left Child >> Right Child<\/em><\/p>\n<p>To understand its concept, we will consider the above binary tree. Its preorder traversal will be:<\/p>\n<p>> b  >> c&#187; alt=&#187;      a  >> b  >> c&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5b9\/f18\/fbe\/5b9f18fbedfc8d93998ebc8e355c38bd.svg&#187; width=&#187;91&#8243; height=&#187;15&#8243;\/><\/p>\n<h2>3. Postorder Traversal  <\/h2>\n<p>Postorder traversal means that the left child comes first in the order then the right child and root node will come. It has the following traversal order:  <\/p>\n<p><em>Left Child >> Right Child >> Root Node  <\/em><\/p>\n<p>To understand its concept, we will consider the previous binary tree. Its postorder traversal will be:  <\/p>\n<p>> c  >> a&#187; alt=&#187; b  >> c  >> a&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a5f\/bc0\/1fa\/a5fbc01fa3782bbd9b5f8e7267e176d6.svg&#187; width=&#187;91&#8243; height=&#187;15&#8243;\/><\/p>\n<p><strong>Example <\/strong> <\/p>\n<p>To understand the concept of binary tree traversals, let us consider the following binary tree. It has an \u20181\u2019 root node.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>For inorder traversal , we have:  <\/p>\n<p>For preorder traversal, we have:  <\/p>\n<p>For postorder traversal, we have:  <\/p>\n<p><strong>Properties of Binary Tree  <\/strong><\/p>\n<p>It has the following properties:  <\/p>\n<ol>\n<li>\n<p>The maximum range of nodes in it is:  <\/p>\n<\/li>\n<\/ol>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>And x= Tree height\u00a0   <\/p>\n<p>    2. The minimum range of nodes in it is:  <\/p>\n<p>    3. Its maximum height for <em>&#8216;n&#8217;<\/em> number of nodes is:  <\/p>\n<p>    4. Its maximum height tree for<em> &#8216;n&#8217; <\/em>number of nodes is:  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p><strong>Application of Binary Tree  <\/strong><\/p>\n<p>It has the following applications:<\/p>\n<ul>\n<li>\n<p>It is used to find duplicate nodes.<\/p>\n<\/li>\n<li>\n<p>It is also used in sorting and in the traversal.<\/p>\n<\/li>\n<li>\n<p>Its practical application is in an organization where binary trees are used to organize data in a sequence.<\/p>\n<\/li>\n<li>\n<p>It is also used in machine learning, database tables, encryption and routing.<\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/560060\/\"> https:\/\/habr.com\/ru\/articles\/560060\/<\/a><br \/><\/br><\/br><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-413611","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/413611","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=413611"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/413611\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=413611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=413611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=413611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}