I was given this coding question for a technical interview:
Given a binary tree, implement a method to populate the list post_ordered_list with the data of the nodes traversed in postorder, iteratively.
For example, given that a binary tree traversing items:
Items in-order: [1, 2, 3, 4, 5, 6, 7]
Items post-order: [1, 3, 2, 5, 7, 6, 4]
I implemented the following binary tree class and it seems to pass all the tests. Here’s a gist of the code.
#!python from queue import LinkedQueue, DeQueue from collections import deque 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 not self.is_leaf() 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?""" # Base case if self.is_leaf(): return 0 # Return one more than the greater of the left height and right height return calculate_height_recursively(node) 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() 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 items_post_order(self): """Return a post-order list of all items in this binary search tree.""" items = [] if not self.is_empty(): # Traverse tree post-order from root, appending each node's item self._traverse_post_order_iterative(self.root, items.append) # Return post-order list of all items in tree return items def _traverse_post_order_iterative(self, node, visit): """Traverse this binary tree with iterative post-order traversal (DFS). Start at the given node and visit each node with the given function. Running time: O(n) Memory usage: Half of the tree. It goes down one half before another """ # Traverse post-order without using recursion (stretch challenge) stack = DeQueue() # It was this, or make sure visit's len is same as the tree while True: # If the node is valid, grab right and left while node: if node.right: stack.enqueue_front(node.right) stack.enqueue_front(node) node = node.left # If it's null, start dequeues else: node = stack.dequeue_front() if node.right and node.right == stack.front(): stack.dequeue_front() stack.enqueue_front(node) node = node.right else: # Put that in the visit. # print(stack.list, visit, "\n\n") visit(node.data) node = None if stack.length() == 0: break # print(stack.list, visit, "\n\n") return visit 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] #items = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15] 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 in-order: {}'.format(tree.items_in_order())) print('items pre-order: {}'.format(tree.items_pre_order())) print('items post-order: {}'.format(tree.items_post_order())) print('items level-order: {}'.format(tree.items_level_order())) if __name__ == '__main__': test_binary_search_tree() Unit test:
#!python from binarytree import BinaryTreeNode, BinarySearchTree import unittest class BinaryTreeNodeTest(unittest.TestCase): def test_items_post_order_with_3_strings(self): # Create a complete binary search tree of 3 strings in level-order items = ['B', 'A', 'C'] tree = BinarySearchTree(items) # Ensure the post-order traversal of tree items is ordered correctly assert tree.items_post_order() == ['A', 'C', 'B'] def test_items_post_order_with_7_numbers(self): # Create a complete binary search tree of 7 items in level-order items = [4, 2, 6, 1, 3, 5, 7] tree = BinarySearchTree(items) # Ensure the post-order traversal of tree items is ordered correctly assert tree.items_post_order() == [1, 3, 2, 5, 7, 6, 4] if __name__ == '__main__': unittest.main() 
