Binary Tree Preorder Traversal

Question

What is the best way to move _add and _preorder methods in class Node to add_node and preorder methods in class BinaryTree such that they have the below class structure:

class Node:
    __init__
    __repr__

class BinaryTree:
    __init__
    add_node
    preorder

Complete Code::

class Node(object):

    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = None
        self.right = None

    def __repr__(self):
        return '{}'.format(self.item)

    def _add(self, value):
        new_node = Node(value)

        if not self.item:
            self.item = new_node
        elif not self.left:
            self.left = new_node
        elif not self.right:
            self.right = new_node
        else:
            self.left = self.left._add(value)
        return self

    def _preorder(self):
        print(self.item)
        if self.left:
            self.left._preorder()
        if self.right:
            self.right._preorder()


class BinaryTree(object):

    def __init__(self):
        self.root = None

    def add_node(self, value):
        if not self.root:
            self.root = Node(value)
        else:
            self.root._add(value)

    def preorder(self):
        if self.root:
            return self.root._preorder()


if __name__ == '__main__':

    binary_tree = BinaryTree()
    print( "Adding nodes 1 to 10 in the tree...")
    for i in range(1, 11):
        binary_tree.add_node(i)

    print()
    print( "Printing preorder...")
    binary_tree.preorder()

Answer 1

class Node(object):

    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = None
        self.right = None

The parameters left and right are not used in the constructor! Remove them, or actually use them.

---

    def _add(self, value):
        new_node = Node(value)

        if not self.item:
            self.item = new_node
        ...

Given self.item is unconditional set in the constructor, this first test seems unnecessary.

        elif not self.left:
            self.left = new_node
        elif not self.right:
            self.right = new_node

Your binary tree does not seem to have any ordering imposed on the left/right nodes. If there is no left node, you create one even if the new value is larger than the current node. Similarly, if there is a left node, but no right node, you create a right node even if the value is smaller than the current node.

        else:
            self.left = self.left._add(value)
        return self

Finally, if both left and right exist, you unconditionally add the new node to the left sub tree, which will create a very unbalanced tree. Moreover, the newly created new_node is discarded, to be recreated by the _add() method one level down, so is wasteful. And the sole purpose of return self seems to be so that there is a return value to assign to self.left, which results in the the original value self.left being assigned to itself, so again useless busy work.

A binary tree does not have any ordering imposed - nodes are added in the following preference: root -> left -> right. Ordering is imposed i[sic] a binary search tree. – Saurabh

With your sample code, adding the values 1 to 10 to your BinaryTree, you get the following "tree":

                           1
                          / \
                         2   3
                        / \
                       4   5
                      / \
                     6   7
                    / \
                   8   9
                  /
                10   

This is not really a binary tree; it is a stick with leaves. It could be represented as a list of tuples: [(1,3), (2,5), (4,7), (6,9), (8,), (10,)].

If you wish to create a general binary tree, which does not impose an ordering, you need to include methods for building the desired tree, such as finding the "5" node, and explicitly adding to the right branch. A generic add_node() doesn't have enough detail to control how the tree is built.

Answer 2

First, some general notes:

1. Eliminate unused complexity. A couple of examples of this are your node constructor, which takes two optional arguments that you never use, and your __repr__, which specifies a format string but doesn't add any extra formatting -- if code is "dead" (i.e. no part of your program uses it), get rid of it so that human readers don't need to read it.

2. You don't strictly need typing in Python code, but it's a good habit to build early since it makes your code easier to check for correctness and it makes it easier for a reader to understand quickly what it does -- for example, in your __main__ function I see that you build a tree with integers in it, but could we pass other types of things as items? Using a TypeVar lets you define what sorts of types it's okay to put in your container (or, if it's only supposed to hold one type, you could just annotate item with that type in order to make that explicit).

3. preorder doesn't seem like a good name for this function, since I don't see that it's "ordering" anything (usually a method name is a verb that says what you're doing, not how you're doing it); the actual effect is to print out the tree. I'd call it something more obvious like print.

Now, as to your question of whether it makes sense to move logic from the Node to the BinaryTree -- IMO when you're working with trees it feels a lot more natural to have the nodes be "smart" so your top level methods can just figure out which subtree should handle a particular task and then delegate it. Here's what your tree might look like with more of the logic moved toward the top; you can judge for yourself whether having the logic in BinaryTree is any better than having it in Node:

from typing import Generic, Optional, TypeVar

# These are the kinds of values that can go in our tree.
V = TypeVar('V', int, float, str) 

class Node(Generic[V]):
    """A node in a binary tree."""
    def __init__(self, item: V):
        self.item: V = item
        self.left: Optional['Node'] = None
        self.right: Optional['Node'] = None

    def __repr__(self) -> str:
        return repr(self.item)


class BinaryTree(Generic[V]):
    """A binary tree."""
    def __init__(self):
        self.root: Optional[Node[V]] = None

    def add_node(self, value: V) -> None:
        """Add the given value to the tree."""
        if not self.root:
            # This is the first node; make it the root.
            self.root = Node(value)
            return

        child = Node(value)
        # Find a spot under the root to add the new child node.
        node = self.root
        while node:
            if value < node.item:
                if node.left:
                    node = node.left
                else:
                    node.left = child
                    return
            elif value > node.item:
                if node.right:
                    node = node.right
                else:
                    node.right = child
                    return
            else:
                return

    def print(self):
        """Print out the tree."""
        def print_node(node: Optional[Node[V]]) -> None:
            if not node:
                return
            print_node(node.left)
            print(node)
            print_node(node.right)
        print_node(self.root)