1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You could use breadth-first search, but I suggest you stick to the depth-first search. What comes to the time complexity, it is \$\Theta(N)\$ since you visit each node 3 times: (1) when descending from the parent node, (2) when returning from the left subtree, and (3) when returning from the right subtree. Another way of verifying the time complexity is to apply the master theorem, which for your recurrence whould, in fact, return \$\Theta(N)\$. \$\endgroup\$ – coderodde Oct 20 '15 at 8:30
  • \$\begingroup\$ By removing the 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\$ – holroy Oct 20 '15 at 8:48
  • \$\begingroup\$ @holroy updated the code with build_tree method definition. \$\endgroup\$ – CodeYogi Oct 20 '15 at 9:53
  • \$\begingroup\$ While you're at it, could you include insert_left and insert_right too? \$\endgroup\$ – ferada Oct 20 '15 at 10:34
  • 1
    \$\begingroup\$ @ferada added the missing definitions. \$\endgroup\$ – CodeYogi Oct 20 '15 at 11:32
2
\$\begingroup\$

The binary tree here consists of either None or TreeNode, so all functions should accept both of these objects as arguments, but is_leaf currently breaks when passed a None node. This representation is also a bit problematic, because if you get a None somewhere, how do you know it's meant to be a tree?

If that case is included, then the first check in is_full can be removed. Otherwise I don't see anything else to optimise, though the results for checking the variables against for None could possibly be cached so the code is minimally faster for huge trees.

Also,

  • the indentation is inconsistent, TreeNode has four spaces in __init__. You know, PEP8.
  • if len(x): is less clear than, e.g. if x:, but in both cases it's relying on conversions from int/list to bool, so not very clear.
\$\endgroup\$
  • \$\begingroup\$ Basically None is considered full. Source: from wiki and Google. \$\endgroup\$ – CodeYogi Oct 20 '15 at 11:34
  • \$\begingroup\$ Not what I meant. None should be handled in is_leaf, as in, if None is a valid tree, then functions working on trees shouldn't break when passed a tree. \$\endgroup\$ – ferada Oct 20 '15 at 11:37
  • \$\begingroup\$ Oh! you mean if node is None: return False I think. \$\endgroup\$ – CodeYogi Oct 20 '15 at 11:40
  • \$\begingroup\$ One more thing, everything was working fine when I found that I need to keep track of the tree node somehow. Now, the things seems to get messy as I have to create a container class for the root. Every methods will be expecting self now, eewwww! \$\endgroup\$ – CodeYogi Oct 23 '15 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.