{"id":27302,"date":"2018-01-20T20:50:31","date_gmt":"2018-01-20T15:20:31","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27302"},"modified":"2018-01-20T20:50:31","modified_gmt":"2018-01-20T15:20:31","slug":"check-whether-given-binary-tree-complete-not-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/check-whether-given-binary-tree-complete-not-2\/","title":{"rendered":"Python Programming-Check whether a given Binary Tree is Complete or not"},"content":{"rendered":"

Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.<\/span><\/p>\n

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. See following examples.<\/p>\n

The following trees are examples of Complete Binary Trees\r\n    1\r\n  \/   \\\r\n 2     3\r\n  \r\n       1\r\n    \/    \\\r\n   2       3\r\n  \/\r\n 4\r\n\r\n       1\r\n    \/    \\\r\n   2      3\r\n  \/  \\    \/\r\n 4    5  6\r\n<\/pre>\n
The following trees are examples of Non-Complete Binary Trees\r\n    1\r\n      \\\r\n       3\r\n  \r\n       1\r\n    \/    \\\r\n   2       3\r\n    \\     \/  \\   \r\n     4   5    6\r\n\r\n       1\r\n    \/    \\\r\n   2      3\r\n         \/  \\\r\n        4    5\r\n<\/pre>\n
The method 2 of level order traversal post can be easily modified to check whether a tree is Complete or not. To understand the approach, let us first define a term \u2018Full Node\u2019. A node is \u2018Full Node\u2019 if both left and right children are not empty (or not NULL).<\/p>\n[ad type=\u201dbanner\u201d]\nThe approach is to do a level order traversal starting from root. In the traversal, once a node is found which is NOT a Full Node, all the following nodes must be leaf nodes.
\nAlso, one more thing needs to be checked to handle the below case: If a node has empty left child, then the right child must be empty.<\/p>\n
Python Programming<\/h4>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Check%20whether%20binary%20tree%20is%20complete%20or%20not%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%23%20Given%20a%20binary%20tree%2C%20return%20true%20if%20the%20tree%20is%20complete%0A%23%20else%20return%20false%0Adef%20isCompleteBT(root)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Base%20Case%3A%20An%20empty%20tree%20is%20complete%20Binary%20tree%0A%20%20%20%20if%20root%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20True%0A%20%0A%20%20%20%20%23%20Create%20an%20empty%20queue%0A%20%20%20%20queue%20%3D%20%5B%5D%0A%20%0A%20%20%20%20%23%20Create%20a%20flag%20variable%20which%20will%20be%20set%20Trye%20%0A%20%20%20%20%23%20when%20a%20non%20ful%20node%20is%20seen%0A%20%20%20%20flag%20%3D%20False%0A%20%0A%20%20%20%20%23%20Do%20level%20order%20traversal%20using%20queue%0A%20%20%20%20queue.append(root)%0A%20%20%20%20while(len(queue)%20%3E%200)%3A%0A%20%20%20%20%20%20%20%20tempNode%20%3D%20queue.pop(0)%20%23%20Dequeue%20%0A%20%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20left%20child%20is%20present%0A%20%20%20%20%20%20%20%20if%20(tempNode.left)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20we%20have%20seen%20a%20non%20full%20node%2C%20and%20we%20see%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20a%20node%20with%20non-empty%20left%20child%2C%20then%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20given%20tree%20is%20not%20a%20complete%20binary%20tree%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20flag%20%3D%3D%20True%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Enqueue%20left%20child%0A%20%20%20%20%20%20%20%20%20%20%20%20queue.append(tempNode.left)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20this%20a%20non-full%20node%2C%20set%20the%20flag%20as%20true%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20flag%20%3D%20True%0A%20%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20right%20cild%20is%20present%0A%20%20%20%20%20%20%20%20if(tempNode.right)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20we%20have%20seen%20a%20non%20full%20node%2C%20and%20we%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20see%20a%20node%20with%20non-empty%20right%20child%2C%20then%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20the%20given%20tree%20is%20not%20a%20compelete%20BT%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20flag%20%3D%3D%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Enqueue%20right%20child%0A%20%20%20%20%20%20%20%20%20%20%20%20queue.append(tempNode.right)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20this%20is%20non-full%20node%2C%20set%20the%20flag%20as%20True%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20flag%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%23%20If%20we%20reach%20here%2C%20then%20the%20tree%20is%20compelete%20BT%0A%20%20%20%20return%20True%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0A%20%0A%22%22%22%20Let%20us%20construct%20the%20following%20Binary%20Tree%20which%0A%20%20%20%20%20%20is%20not%20a%20complete%20Binary%20Tree%0A%20%20%20%20%20%20%20%20%20%20%20%201%0A%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%5C%0A%20%20%20%20%20%20%20%20%202%20%20%20%20%203%0A%20%20%20%20%20%20%20%20%2F%20%5C%20%20%20%20%20%5C%0A%20%20%20%20%20%20%204%20%20%205%20%20%20%20%206%0A%20%20%20%20%22%22%22%0Aroot%20%3D%20Node(1)%0Aroot.left%20%3D%20Node(2)%0Aroot.right%20%3D%20Node(3)%0Aroot.left.left%20%3D%20Node(4)%0Aroot.left.right%20%3D%20Node(5)%0Aroot.right.right%20%3D%20Node(6)%0A%20%0Aif%20(isCompleteBT(root))%3A%0A%20%20%20%20print%20%22Complete%20Binary%20Tree%22%0Aelse%3A%0A%20%20%20%20print%20%22NOT%20Complete%20Binary%20Tree%22%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
NOT Complete Binary Tree<\/pre>\n
Time Complexity:<\/em> O(n) where n is the number of nodes in given Binary Tree<\/p>\n
Auxiliary Space: <\/em>O(n) for queue.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Check whether given binary tree complete not Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,73012,4148,80124],"tags":[81370,81368,81365,81366,81372,81367,81362,81363,81364,81373,81374,81376,81369,81371,81375],"class_list":["post-27302","post","type-post","status-publish","format-standard","hentry","category-coding","category-data-structures","category-python","category-queue","tag-almost-complete-binary-tree","tag-check-if-binary-tree-is-complete-c","tag-check-if-binary-tree-is-perfect","tag-check-if-binary-tree-is-perfectly-balanced","tag-complete-binary-tree-algorithm","tag-complete-binary-tree-code-c","tag-complete-binary-tree-definition-example","tag-complete-binary-tree-java","tag-complete-binary-tree-program-in-c","tag-extended-binary-tree","tag-incomplete-binary-tree","tag-perfect-binary-tree","tag-perfect-binary-tree-c","tag-strictly-binary-tree","tag-types-of-binary-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27302","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=27302"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27302\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27302"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27302"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}