Problem statement
Given a node check whether the sub-tree rooted at given node is full binary tree or not.
Definition
A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.
Solution
class TreeNode(object):
"""Node of a Binary tree."""
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def __str__(self):
return "{0}".format(self.key)
def insert_left(parent, node):
parent.left = node
return parent
def insert_right(parent, node):
parent.right = node
return parent
def is_leaf(node):
"""Checks whether given node is leaf."""
return node.left is None and node.right is None
def is_full(node):
"""Checks if the subtree rooted at the given node is full.
A Binary tree is full when every node other than leaves
has two children.
"""
if node is None:
return True
if is_leaf(node):
return True
if node.left is not None and node.right is not None:
return is_full(node.left) and is_full(node.right)
return False
def build_tree(inorder, preorder):
"""Builds a Binary Tree from given inorder and preorder traversal.
Steps:
1. Take the first element from the preorder list.
2. Get the index of the element from inorder list.
3. Set the element as root.
4. Take all elements left to root from inorder list.
5. Take all elements right to root from inorder list.
6. Calculate preorder list for left and right subtree respectively.
7. Repeat from step 1 for each subtree.
"""
def recurse(node, inorder, preorder):
if len(preorder) == 1:
return TreeNode(preorder)
key = preorder[0]
root_index = inorder.find(key)
inorder_left = inorder[:root_index]
inorder_right = inorder[root_index+1:]
preorder_left = preorder[1:len(inorder_left)+1]
preorder_right = preorder[root_index+1:]
node = TreeNode(key)
if len(inorder_left):
insert_left(node, recurse(None, inorder_left, preorder_left))
if len(inorder_right):
insert_right(node, recurse(None, inorder_right, preorder_right))
return node
return recurse(None, inorder, preorder)
import unittest
class TestBinaryTree(unittest.TestCase):
def test_isFull(self):
root = build_tree('DBEAFIC', 'ABDEICF')
self.assertTrue(is_full(root))
root = build_tree('DBEAFC', 'ABDECF')
self.assertFalse(is_full(root))
if __name__ == '__main__':
unittest.main()
Time Complexity
It seems its a \$O(N)\$ where \$N\$ is the number of nodes in the given Binary Tree.
I am also interested in mathematical approach for estimating complexity of these kind of problems. So, here is my initial approach: \$T(n) = T(n/2) + T(n/2) + 2\$
Is there more cleaner way? Also, the above solution uses a DFS approach i.e. checking every node in a tree. Can we optimize it?
Note
I have extracted away the definition of build_tree
as its not important here.
build_tree()
you're also making it harder to run actual tests on your code... We now either have to make dry runs, or build a tree of our own. \$\endgroup\$build_tree
method definition. \$\endgroup\$insert_left
andinsert_right
too? \$\endgroup\$