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