Binary Search Tree BFS iteratively

Question

I was given this coding question for a technical interview:

Given a binary tree, implement a method to populate the list level_ordered_list with the data of the nodes traversed level-order, iteratively.

For example, given that a binary tree traversing items:

Items in-order: [1, 2, 3, 4, 5, 6, 7]

items level-order: [4, 2, 6, 1, 3, 5, 7]

I implemented the following binary tree class and it seems to pass all the tests. Here's a gist of the code.

from collections import deque
from queue import LinkedQueue, DeQueue
class BinaryTreeNode(object):
 def __init__(self, data):
 """Initialize this binary tree node with the given data."""
 self.data = data
 self.left = None
 self.right = None
 def __repr__(self):
 """Return a string representation of this binary tree node."""
 return 'BinaryTreeNode({!r})'.format(self.data)
 def is_leaf(self):
 """Return True if this node is a leaf (has no children)."""
 # Check if both left child and right child have no value
 return self.left is None and self.right is None
 def is_branch(self):
 """Return True if this node is a branch (has at least one child)."""
 # Check if either left child or right child has a value
 return self.left is not None or self.right is not None
 def height(self):
 """Return the height of this node (the number of edges on the longest
 downward path from this node to a descendant leaf node).
 Best and worst case running time: O(N) under what conditions?"""
 right_height, left_height = 0, 0
 # Base case
 if self.is_leaf():
 return 0
 # Return one more than the greater of the left height and right height
 if self.right:
 right_height = self.right.height() # use ternary
 if self.left:
 left_height = self.left.height()
 return max(left_height, right_height) + 1
class BinarySearchTree(object):
 def __init__(self, items=None):
 """Initialize this binary search tree and insert the given items."""
 self.root = None
 self.size = 0
 if items is not None:
 for item in items:
 self.insert(item)
 def __repr__(self):
 """Return a string representation of this binary search tree."""
 return 'BinarySearchTree({} nodes)'.format(self.size)
 def is_empty(self):
 """Return True if this binary search tree is empty (has no nodes)."""
 return self.root is None
 def height(self):
 """Return the height of this tree (the number of edges on the longest
 downward path from this tree's root node to a descendant leaf node).
 n; going to go through everything"""
 # Check if root node has a value and if so calculate its height
 #return self.root.height()
 if self.root:
 return self.root.height()
 else:
 return 0
 def contains(self, item):
 """Return True if this binary search tree contains the given item.
 log(n): it's going to traverse based on height, which is log(n) """
 # Find a node with the given item, if any
 node = self._find_node(item)
 # Return True if a node was found, or False
 return node is not None
 def search(self, item):
 """Return an item in this binary search tree matching the given item,
 or None if the given item is not found.
 log(n): it's going to traverse based on height, which is log(n)"""
 # Find a node with the given item, if any
 node = self._find_node(item)
 # Return the node's data if found, or None
 return node.data if node else None
 def insert(self, item):
 """Insert the given item in order into this binary search tree.
 If it's empty, well, it's 1
 Otherwise, log(n); we know where we're heading"""
 # Handle the case where the tree is empty
 if self.is_empty():
 # Create a new root node
 self.root = BinaryTreeNode(item)
 # Increase the tree size
 self.size += 1
 return
 # Grab parent of where node should be
 parent = self._find_parent_node(item)
 # Check if the given item should be inserted left of parent node
 if item < parent.data:
 parent.left = BinaryTreeNode(item)
 # Check if the given item should be inserted right of parent node
 elif item > parent.data:
 parent.right = BinaryTreeNode(item)
 self.size += 1
 def items_level_order(self):
 """Return a level-order list of all items in this binary search tree."""
 items = []
 if not self.is_empty():
 # Traverse tree level-order from root, appending each node's item
 self._traverse_level_order_iterative(self.root, items.append)
 # Return level-order list of all items in tree
 return items
 def _traverse_level_order_iterative(self, start_node, visit):
 """Traverse this binary tree with iterative level-order traversal (BFS).
 Start at the given node and visit each node with the given function.
 # Create queue to store nodes not yet traversed in level-order
 Remove and return the item at the back of this queue,"""
 queue = DeQueue()
 queue.enqueue_front(start_node)
 while queue.is_empty() == False:
 node = queue.dequeue_front()
 visit(node.data)
 if node.left != None:
 queue.enqueue_back(node.left)
 if node.right != None:
 queue.enqueue_back(node.right)
# I include my codes to way the binary search tree with the items
def test_binary_search_tree():
 # Create a complete binary search tree of 3, 7, or 15 items in level-order
 # items = [2, 1, 3]
 items = [4, 2, 6, 1, 3, 5, 7]
 print('items: {}'.format(items))
 tree = BinarySearchTree()
 print('tree: {}'.format(tree))
 print('root: {}'.format(tree.root))
 print('\nInserting items:')
 for item in items:
 tree.insert(item)
 print('insert({}), size: {}'.format(item, tree.size))
 print('root: {}'.format(tree.root))
 print('\nSearching for items:')
 for item in items:
 result = tree.search(item)
 print('search({}): {}'.format(item, result))
 item = 123
 result = tree.search(item)
 print('search({}): {}'.format(item, result))
 print('\nTraversing items:')
 print('items level-order: {}'.format(tree.items_level_order()))
if __name__ == '__main__':
 test_binary_search_tree()
Unit testing:
#!python
from binarytree import BinaryTreeNode, BinarySearchTree
import unittest
class BinaryTreeNodeTest(unittest.TestCase):
 def test_search_with_3_items(self):
 # Create a complete binary search tree of 3 items in level-order
 items = [2, 1, 3]
 tree = BinarySearchTree(items)
 assert tree.search(1) == 1
 assert tree.search(2) == 2
 assert tree.search(3) == 3
 assert tree.search(4) is None
 def test_search_with_7_items(self):
 # Create a complete binary search tree of 7 items in level-order
 items = [4, 2, 6, 1, 3, 5, 7]
 tree = BinarySearchTree(items)
 for item in items:
 assert tree.search(item) == item
 assert tree.search(8) is None
 def test_search_with_3_strings(self):
 # Create a complete binary search tree of 3 items in level-order
 items = ['B', 'A', 'C']
 tree = BinarySearchTree(items)
 assert tree.search('A') == 'A'
 assert tree.search('B') == 'B'
 assert tree.search('C') == 'C'
 assert tree.search('D') is None
 def test_search_with_7_strings(self):
 # Create a complete binary search tree of 7 items in level-order
 items = ['D', 'B', 'F', 'A', 'C', 'E', 'G']
 tree = BinarySearchTree(items)
 for item in items:
 assert tree.search(item) == item
 assert tree.search('H') is None
 def test_insert_with_3_items(self):
 # Create a complete binary search tree of 3 items in level-order
 tree = BinarySearchTree()
 tree.insert(2)
 assert tree.root.data == 2
 assert tree.root.left is None
 assert tree.root.right is None
 tree.insert(1)
 assert tree.root.data == 2
 assert tree.root.left.data == 1
 assert tree.root.right is None
 tree.insert(3)
 assert tree.root.data == 2
 assert tree.root.left.data == 1
 assert tree.root.right.data == 3
 def test_insert_with_7_items(self):
 # Create a complete binary search tree of 7 items in level-order
 items = [4, 2, 6, 1, 3, 5, 7]
 tree = BinarySearchTree()
 for item in items:
 tree.insert(item)
 assert tree.root.data == 4
 assert tree.root.left.data == 2
 assert tree.root.right.data == 6
 assert tree.root.left.left.data == 1
 assert tree.root.left.right.data == 3
 assert tree.root.right.left.data == 5
 assert tree.root.right.right.data == 7
if __name__ == '__main__':
 unittest.main()

Answer 1

[Caveat: This review is premised on a rigorous technical interview context. It takes the specification literally.]

High order bit

To me, the code does not really meet the specification.

1. The specification says that a binary tree is "given". The code explicitly creates a separate implementation of a binary search tree without reference to the given.
2. There is no method which takes a sorted list and returns a level_ordered representation of the list.

In other words, the specification requests a method level_ordered that operates on lists:

level_ordered([1, 2, 3, 4, 5, 6, 7]) -> [4, 2, 6, 1, 3, 5, 7]

and the specification suggests that the method use an existing implementation of a binary tree.

Remarks on Code details

• The code is reasonably compact, organized and documented.
• The code implements superfluous methods such as leaf, branch, depth that are not required by the specification, not utilized internally, and not covered by tests. In particular, the method contains will not be needed by a method level_ordered(aList) that operates on lists.

Alternative Implementation

The problem can be met using list comprehensions. Since this approach does not use a binary tree either, it may not meet the specification.

1: def level_ordered(sorted_input):
2: length = len(sorted_input)
3: index = list(range(1,length+1))
4: out = []
5: depth = math.ceil(math.log2(length))
6: depths = [2**i for i in list(range(depth,-1,-1))]
7: for d in depths:
8: out += [i for i in index if i % d == 0 and not i % (d * 2) == 0]
9: return [sorted_input[v-1] for v in out]

Notes

• 3: Because the input list is sorted, the transformation can be performed on the indexes of the input. Because modulos are used to select values, index starts at 1 rather than 0.

• 5: The total running time is O(n log n) which is equivalent to the O (log n) average insertion time for a binary search tree times n insertions.

• 6: Zero is necessary because 2**i == 1 when i == 0.

• 9: The values from the input list are referenced by index so that

  level_ordered(['a', 'b', 'c', 'd', 'e', 'f', 'g']) == ['d', 'b', 'f', 'a', 'c', 'e', 'g']

Discussion of difficulty

For me the alternative implementation was non-obvious and the result of many hours of trial and error and Googling Python syntax. I could never have white-boarded it. I wrote the implementation after writing "High Order Bit" and "Remarks on Code details" because I wanted to be sure that my interpretations of the specification were plausible.

Though O(n log n) time is good, I have a hunch that O(n) may be possible because the list is already sorted. O(n log n) is the best possible sorting for random data and already sorted data suggests most of the work has been done. For example, the first value is always on the lowest level of the tree, the last value is on the second lowest level except when log2(n) is an integer, and so on. In other words, the list comprehensions reflect a function that can be applied to the indexes.

Answer 2

Much of the code looks good. Some comments could be clearer, and there are some correctness issues.

In is_leaf(), please strike this redundant remark:

 # Check if both left child and right child have no value

The code makes perfect sense as it stands. Code should say what is specific, and comments should speak in generalities that wouldn't be obvious from the code.

Similar remarks for is_branch(). Thank you for supplying docstrings, that is very nice. The one for is_branch() might mention the standard term of "interior node". The "return True if this node is a branch" phrasing is obvious already, given the (well chosen) function name. The code is redundant, as it is just an expansion of De Morgan's rule for the function above. Better to simply return not is_leaf() if you feel this function needs to be part of your public API.

In height(), shorten the docstring to just the parenthetical. The performance question would go better in a comment. Or add a comment that points out a degenerate tree created in sorted order will suffer \$\mathcal{O}(n)\$ performance, and the best case is \$\mathcal{O}(\log n)\$ for a balanced tree.

Where you defined __repr__(), twice, it would probably be better to stick to __str__(). Repr is supposed to show enough to recreate an object, while str just needs to be human readable.

The BST height() docstring is awkwardly phrased; it correctly uses "longest" but should pair that with "any". Better to simply copy the docstring of the function it calls.

The contains() docstring neglects the unbalanced case, e.g. cost to search a BST created from sorted input items. Similarly for insert().

This code doesn't make sense to me:

 if item < parent.data:
 parent.left = BinaryTreeNode(item)

Suppose the parent already had a left branch. What, we just nuke it, overwriting it? Similarly for right branch.

This code doesn't make sense to me:

 self.size += 1

In the equality case, we don't create any new nodes, yet we report tree growth?

 while queue.is_empty() == False:

This would be more naturally phrased as while not queue.is_empty():.

 if node.left != None:

Please phrase this as is not None. Similarly for right.

Thank you for including your tests. Consider passing multiple permutations to the code under test.

In BinaryTreeNodeTest, the asserts work fine. Consider using self.assertEqual() instead, as it produces a more informative result in the event of failure.

Answer 3

There are no such LinkedQueue and DeQueue classes in the queue module, so I am not sure how you succeeded to run the program as you instantiated DeQueue in _traverse_level_order_iterative() function, and you could have got an ImportError exception at the very beginning:

>>> from queue import LinkedQueue
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
ImportError: cannot import name 'LinkedQueue'
>>> from queue import DeQueue
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
ImportError: cannot import name 'DeQueue'

• NinjaG: I made the snippet for my LinkedQueue class available at this GitHub link: gist.github.com/Jeffchiucp/39f6d896e766cf3a33dc63f9cbc3a445
• Billal BEGUERADJ: Ok ... but there is a built-in module named queue, a good practice is that you choose a different name for your module, not only to avoid confusion but also to avoid unexpected behaviors.