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.

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

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)

• kyrill: 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.
• Samwise: 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. :)
• AJNeufeld: 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.
• Saurabh: 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.