recursion on a tree with different type of nodes in python

Question

I am building a Tree class that consists of inner nodes (denoted by the class Inner) and leaf nodes (denoted by the class Node).

class Node(object):
    def __init__(self,bits,data):
        self.bits = bits
        self.data = data


class Inner(object):
    def __init__(self):
        self.bits = ''
        self.c0  = None
        self.c1 = None


class Tree(object):
    def __init__(self):
        self.root = None

   def insert_Item(self,key,datastr):
   #code goes here

I can insert both leafs and inner nodes using insert method.

t = Tree()
t.insert('1111', 'A')
t.insert('1110', 'B')

The problem occurs with recursive formulation of insert method. I cannot call self.root.c0.insert() or self.root.c1.insert() assuming self.root.c0 and self.root.c1 points to Inner nodes. This is because Inner class does not have insert function.

What can i do to make insert method work on all three classes in a recursive fashion? Similarly i cannot do tree traversal as i get Error that Inner object has no attribute 'data'

Why don't you make a parent class that all of them inherit from and has the implementation of the insert method? — solarc, Mar 28 '16 at 22:39
A leaf is just a node with no children. Why do you need a entirely separate class to identify that? — OneCricketeer, Mar 28 '16 at 22:41
@cricket_007. This is because of this crazy specification http://stackoverflow.com/questions/36166004/prefix-tree-type-and-insertion — user2065276, Mar 28 '16 at 22:45
Ohh, I see. Yeah, I don't miss complex binary tree problems at all. — OneCricketeer, Mar 28 '16 at 22:48
@cricket_007 Here is the mighty code that works but without the elegance of recursion http://pastebin.com/7aHw7Aj5 — user2065276, Mar 28 '16 at 22:52
There are many references on how to implement a trie datastructure in Python, see e.g. http://stackoverflow.com/questions/11015320/how-to-create-a-trie-in-python — thebjorn, Mar 28 '16 at 23:25

manglano · Accepted Answer · 2016-03-28T23:33:09.240

Consider changing your implementation, so the tree only has nodes, traversal methods are a class method of the Node class, and the identity of the node as inner or leaf is determined as a function of whether the node has children or no children.

Generally, in terms of OOP, you want to implement as few classes as possible--as few as necessary to fully disambiguate the program's function while also providing the enhanced utility necessary for other programmers. Before implementing a new subclass, think: can another class perform the methods of this class without using polymorphism?

class Node(object):

      leftNode = None
      rightNode = None
      root = None

      def __init__(self,data,bit):
         self.bits = bit
         self.data = data
    /* I will make an assumption about the structure, left us assume the tree is simple, and preferentially populates the left subtree */
      def insert_Item(self,data,bit):
         if (leftNode == None):
              self.leftNode = Node(data,bit)
         elif (rightNode === None):
              self.rightNode = Node(data,bit)
         else:
              self.leftNode.insert_Item(data, bit)

class Tree(object):
    root = None
    def __init__(self, rootNode):
        self.root = rootNode

    def add_data(self,data,bit):
        self.root.insert_Item(data,bit)

With a little modification, these two classes will do everything you need. I recommend consulting this text as a primer: http://interactivepython.org/runestone/static/pythonds/index.html

can you please give an example case explaining your above answer — user2065276, Mar 28 '16 at 23:07

recursion on a tree with different type of nodes in python

1 Answers1