Binary Tree Preorder Traversal

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

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:
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

if not self.root:
self.root = Node(value)
else:

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

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



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

• A binary tree does not have any ordering imposed - nodes are added in the following preference: root -> left -> right. Ordering is imposed i a binary search tree. Feb 17 '20 at 23:43

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)

• Preorder traversal of a tree is a well-known and well-defined term. I don't see anything wrong with it, although I do agree that the printing functionality is unnecessarily hard-coded. Your reimplementation prints the tree in-order, which is not what OP wanted. No offense intended, but I suggest you do some studying on basic algorithms. Feb 17 '20 at 2:08
• Made that comment a little clearer. Generally you want to name a function by what it does rather than how, why, or where it does it -- function names like recursive and helper and iterate show up a lot in sample code (and code written by new grads) but they're bad habits to get into. :) Feb 17 '20 at 2:33
• You have completely changed the behaviour of add_node(). The OP’s code did not enforce a less-than/greater-than ordering to the left/right children. Probably a bug in the OP’s implementation, but you’ve altered the behaviour without even mentioning it. Additionally, your implementation does not allow the tree to contain duplicate values. Finally, the __repr__ function is not “dead” code; it changes the representation of a node into the string of the value contained that node. Feb 17 '20 at 6:58
• I agree with all your points, but the add_node method in your answer is for a binary search tree and NOT a binary tree. Also, the print method is inorder and NOT preorder. Feb 17 '20 at 23:08