Check if a Binary Tree is full

Question

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.

Answer 1

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.