0

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?

Improve this question
1
  • 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. Commented Jul 14, 2015 at 14:13

1 Answer 1

Reset to default
2

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).

Improve this answer
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.