{"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=”banner”]\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
 
 <\/div> 
# Check whether binary tree is complete or not # A binary tree nodeclass Node:     # Constructor to create a new node    def __init__(self, data):        self.data = data         self.left = None        self.right = None # Given a binary tree, return true if the tree is complete# else return falsedef isCompleteBT(root):         # Base Case: An empty tree is complete Binary tree    if root is None:        return True     # Create an empty queue    queue = []     # Create a flag variable which will be set Trye     # when a non ful node is seen    flag = False     # Do level order traversal using queue    queue.append(root)    while(len(queue) > 0):        tempNode = queue.pop(0) # Dequeue          # Check if left child is present        if (tempNode.left):                         # If we have seen a non full node, and we see            # a node with non-empty left child, then the            # given tree is not a complete binary tree            if flag == True :                return False             # Enqueue left child            queue.append(tempNode.left)             # If this a non-full node, set the flag as true        else:            flag = True         # Check if right cild is present        if(tempNode.right):                             # If we have seen a non full node, and we             # see a node with non-empty right child, then            # the given tree is not a compelete BT            if flag == True:                return False             # Enqueue right child            queue.append(tempNode.right)                     # If this is non-full node, set the flag as True        else:            flag = True             # If we reach here, then the tree is compelete BT    return True  # Driver program to test above function """ Let us construct the following Binary Tree which      is not a complete Binary Tree            1          \/   \\         2     3        \/ \\     \\       4   5     6    """root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.right = Node(6) if (isCompleteBT(root)):    print "Complete Binary Tree"else:    print "NOT Complete Binary Tree" # This code is contributed by Nikhil Kumar Singh(nickzuck_007)<\/code><\/pre> <\/div>\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=”banner”]\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}]}}