{"id":26945,"date":"2017-12-28T21:47:13","date_gmt":"2017-12-28T16:17:13","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26945"},"modified":"2017-12-28T21:47:13","modified_gmt":"2017-12-28T16:17:13","slug":"binary-tree-properties","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/binary-tree-properties\/","title":{"rendered":"Binary Tree (Properties)"},"content":{"rendered":"<p>We have discussed <a href=\"http:\/\/quiz.geeksforgeeks.org\/binary-tree-set-1-introduction\/\" target=\"_blank\" rel=\"noopener\">Introduction to Binary Tree in set 1<\/a>. In this post, properties of binary are discussed.<\/p>\n<p><em><br \/>\n<strong>1) The maximum number of nodes at level \u2018l\u2019 of a binary tree is 2<sup>l-1<\/sup><\/strong><\/em>.<br \/>\nHere level is number of nodes on path from root to the node (including root and node). Level of root is 1.<br \/>\nThis can be proved by induction.<br \/>\nFor root, l = 1, number of nodes = 2<sup>1-1<\/sup> = 1<br \/>\nAssume that maximum number of nodes on level l is 2<sup>l-1<\/sup><br \/>\nSince in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2<sup>l-1<\/sup><br \/>\n<em><strong>2) Maximum number of nodes in a binary tree of height \u2018h\u2019 is 2<sup>h<\/sup> \u2013 1<\/strong><\/em>.<br \/>\nHere height of a tree is maximum number of nodes on root to leaf path. Height of a leaf node is considered as 1.<br \/>\nThis result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So maximum number of nodes in a binary tree of height h is 1 + 2 + 4 + .. + 2<sup>h-1<\/sup>. This is a simple geometric series with h terms and sum of this series is 2<sup>h<\/sup> \u2013 1.<br \/>\nIn some books, height of a leaf is considered as 0. In this convention, the above formula becomes 2<sup>h+1<\/sup>\u2013 1<\/p>\n[ad type=&#8221;banner&#8221;]\n<em><strong>3) In a Binary Tree with N nodes, minimum possible height or minimum number of levels is\u00a0 \u2308 Log<sub>2<\/sub>(N+1) \u2309 \u00a0 <\/strong><\/em><br \/>\nThis can be directly derived from point 2 above. If we consider the convention where height of a leaf node is considered as 0, then above formula for minimum possible height becomes \u00a0 \u2308 Log<sub>2<\/sub>(N+1) \u2309 \u2013 1<br \/>\n<em><strong>4) A Binary Tree with L leaves has at least \u00a0 \u2308 Log<sub>2<\/sub>L \u2309 + 1 \u00a0 levels<\/strong><\/em><br \/>\nA Binary tree has maximum number of leaves when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L.<\/p>\n<pre>   L   &lt;=  2<sup>l-1<\/sup>  [From Point 1]\r\n   Log<sub>2<\/sub>L =   \u2308 Log<sub>2<\/sub>L \u2309 + 1<\/pre>\n<p><em><strong>5) In Binary tree, number of leaf nodes is always one more than nodes with two children<\/strong><\/em>.<\/p>\n<pre>   L = T + 1\r\nWhere L = Number of leaf nodes\r\n      T = Number of internal nodes with two children<\/pre>\n<p>See <a href=\"http:\/\/www.geeksforgeeks.org\/handshaking-lemma-and-interesting-tree-properties\/\" target=\"_blank\" rel=\"noopener\">Handshaking Lemma and Tree<\/a> for proof.<\/p>\n<p>In the next article on tree series, we will be discussing <a href=\"http:\/\/quiz.geeksforgeeks.org\/binary-tree-set-3-types-of-binary-tree\/\" target=\"_blank\" rel=\"noopener\">different types of Binary Trees and their properties<\/a>.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Binary Tree Properties &#8211; Binary Tree &#8211; Here level is number of nodes on path from root to the node (including root and node). Level of root is 1.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80139],"tags":[70287,70296,80452,70303,70285,70489,80415,80451],"class_list":["post-26945","post","type-post","status-publish","format-standard","hentry","category-binary-tree-divide-and-conquer","tag-binary-tree-algorithm","tag-binary-tree-example","tag-binary-tree-height","tag-binary-tree-in-c","tag-binary-tree-traversal","tag-complete-binary-tree","tag-sorted-binary-tree","tag-types-of-binary-tree-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26945","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26945"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26945\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26945"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26945"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26945"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}