current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 0 down vote favorite

I am shifting from procedural C programming to OOP Python programming and I faced some problems while implementing binary search trees.

I cannot make my Tree_Node null in case of deleting it. In C I could do this because I would handle the case in the function as follows:

    void insert(Node tree, int key)
    {
      if (tree == null)
      {
        // deal with it
      }
    }

But in python using OOP I cannot make my Tree_Node null as it is a class and it contains all my methods.

class Tree:
  # Tree methods

t = Tree()
t = None  # Cannot do this as then how would I call its methods

Q1) How do you solve this problem in general? (not just for binary search trees) What is the standard OOP practice for this?

Second problem is that I cannot modify self in Python. In C I could do as follows:

void foo(Node tree, int key)
{
  tree = tree->left
}

But in python's class I cannot do as follows:

class Tree:
  def foo(self, key):
    self = self.left  # Cannot do this

Q2) So how do I solve such problems? Any standard OOP practice?

Q3) A meta question. I thought OOP makes programming easier. But in this case, I find it much tough to implement a rather simple data structure. It adds restrictions such as not able to modify self, not able to make it null etc. Am I doing something wrong?

share|improve this question
    
The Tree class should contain both methods and data. So you would have some properties (left and right I assume from your subsequent snippets) that would represent the value of the nodes, allowing you to say t.left = None. –  Michael Jul 14 at 14:13

1 Answer 1

up vote 2 down vote

The OOP way is to combine together polymorphism and recursion. A binary tree is defined as either empty or a set of value, left and right where both left and right are binary trees. To represent it properly left and right must be binary tree themselves, even if they are empty.

To represent that in object oriented way, we'll have a tree base class and node and empty subclasses. These subclasses will contain method implementations that access the fields directly, and the base class can contain methods that use these methods:

from abc import ABCMeta, abstractmethod

class Tree(metaclass=ABCMeta):
    @abstractmethod
    def infix(self):
        pass

    def set(self):
        return set(self.infix())


class EmptyTree(Tree):
    def infix(self):
        yield from ()


class TreeNode(Tree):
    def __init__(self, value, left=EmptyTree(), right=EmptyTree()):
        self.value = value
        self.left = left
        self.right = right

    def depth(self):
        return 1 + max(self.left.depth(), self.right.depth())

    def infix(self):
        yield from self.left.infix()
        yield self.value
        yield from self.right.infix()


tree = TreeNode(1, TreeNode(2), TreeNode(3, EmptyTree(), TreeNode(4)))

assert list(tree.infix()) == [2, 1, 3, 4]

assert tree.set() == {1, 2, 3, 4}

assert list(EmptyTree().infix()) == []

assert EmptyTree().set() == set()

The infix method is in the subclasses, because it behaves differently for EmptyTree and for TreeNode. The set method is defined in the base class, because it only relies on the infix method that is defined for all trees.

The idea is that you don't check yourself if a tree is empty - you simply invoke it's methods, which may differ based on whether the tree is empty(instance of EmptyTree) or not(instance of TreeNode).

share|improve this answer
1  
+1! In fact, the difference here is not so much about procedural vs. OO design, but more about Abstract Data Types vs. Object-Oriented Data Abstraction. (See On Understanding Data Abstraction, Revisited by William R. Cook) –  Jörg W Mittag Jul 14 at 15:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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