search

jeff1evesque / interview-twitter

Least Common Ancestor
2 stars 0 forks source link

determine a representation for the binary tree #1

Open jeff1evesque opened 10 years ago

jeff1evesque commented 10 years ago

We need to determine how to represent the binary tree, preferably as an external file.

jeff1evesque commented 10 years ago

04546d1: contains the input file (input.py) needed to generate the binary search tree. Note: it will need to follow a fixed format, as the input will need to be parsed.

e8b545a: contains the file (least-common-ancestor.py) needed to consume the input data (input.py), and generate the binary search tree, for now. Later, this file will determine the least common ancestor.

jeff1evesque commented 10 years ago

098153c: consumes input.py file, and prints its content line by line. It unfortunately, prints comment lines as well:

MacBook-Pro-15:least-common-ancestor jeffrey$ python least-common-ancestor.py
['# input.py file is used to generate the binary tree \n', '\n', "'''\n", 'The following commands\n', '\n', 'root = Node(3)\n', '\n', 'tree = BinarySearchTree(root)\n', '\n', 'tree.add(55)\n', 'tree.add(2)\n', 'tree.add(3)\n', 'tree.add(30)\n', 'tree.add(100)\n', 'tree.add(45)\n', 'tree.add(1)\n', 'tree.add(43)\n', 'tree.add(48)\n', 'tree.add(25)\n', 'tree.add(21)\n', '\n', 'generates a tree structure as follows\n', '\n', '                 3\n', '                / \\\n', '               /   \\\n', '              /     \\\n', '             2      55\n', '            / \\    /  \\\n', '           1   3  30   100\n', '                 /  \\\n', '               25   45\n', '               /   /  \\\n', '             21   43   48\n', "'''\n", '\n', 'root = Node(7)\n', '\n', 'tree = BinarySearchTree(root)\n', '\n', 'tree.add(23)\n', 'tree.add(1)\n', 'tree.add(14)\n', 'tree.add(53)\n', 'tree.add(22)\n']
hi
jeff1evesque commented 10 years ago

a393954: ignores single line comments, and new lines.

jeff1evesque commented 10 years ago

5f36ff9: we've reinserted the comment in a different pull-request https://github.com/jeff1evesque/least-common-ancestor/pull/3

jeff1evesque commented 10 years ago

f89ae90: both root, and tree values are contained in its own square brackets within the file input.txt. For example:

root = [7]
tree = [23, 1, 14, 53, 22]
jeff1evesque commented 10 years ago

d5eab22: we have two elif (else-if) conditions that determine if the current line of the file input.txt ( being opened from least-common-ancestor.py ) starts with root, or tree. Then, we parse the associated values contained within the square brackets, split() them on commas, and assign them to a list structure. For example:

tree = line.partition('[')[-1].rpartition(']')[0].split(',')