#StackBounty: #tree #grammars #context-free Example of context-free tree language which can not be generated by monadic CFTG

Bounty: 50

Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (MCFTG).

In other words, I am looking for such a non-monadic CFTG for which it is not possible to construct an equivalent (MCFTG).

The all examples of CFTG’s which exist in papers are essentially monadic CFTG.

I am still trying to build such a grammar by myself. But may be somebody already knows such an example and could share it as an answer. I deeply appreciate any help.


Get this bounty!!!

#StackBounty: #python #tree #reinventing-the-wheel #breadth-first-search Binary Search Tree BFS iteratively

Bounty: 50

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


Get this bounty!!!

#Tree #Traversals

Below is the Python code for traversing trees in various recursive modes like In order, Preorder, Post Order and their reverse orders…

The code is provided in python, but can be easily translated to Java/JS/PHP etc

CodeEval: PASS TRIANGLE

CHALLENGE DESCRIPTION:

By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.

   5
  9 6
 4 6 8
0 7 1 5

5 + 9 + 6 + 7 = 27

INPUT SAMPLE:

Your program should accept as its first argument a path to a filename. Input example is the following:

5
9 6
4 6 8
0 7 1 5

You make also check full input file which will be used for your code evaluation.

OUTPUT SAMPLE:

The correct output is the maximum sum for the triangle. So for the given example the correct answer would beĀ 27

Solution