Bite 378. Organizational Chart

Of all the types of questions you are likely to encounter during a technical interview - assuming the interview is focused on data structures and algorithms - those related to 'trees' and 'graphs' are arguably the most common.  

Although a full discussion of graph theory is beyond the scope of this Bite, any such discussion begins with trees, which is where we'll start.

Trees

In computer science, tree, is an abstract data structure often used to model hierarchical relationships and resembling, more or less, an actual tree in nature - excepted inverted, with its root at the top and leaves at the bottom. 

A tree consists of nodes connected by edges. 

A node, in turn, stores data (of any type) as well as pointers to other nodes. A node's nodes are called its children, and a node with no children is called a leaf. 

Binary Trees

A binary tree is a type of tree with a specific constraint - each node in a binary tree can have a maximum of two children. 

Here a picture may help:

This tree has a depth of three and consists of the following:

- O -> root node with two children, 1 and 2. 

- 1 -> node with two children, 3 and 4. 

- 3 -> a leaf (node with no children)

- 4 -> leaf 

- 2 -> child node of 0 with one child, 5.

- 5 -> leaf

Exercise

Given a company org chart, determine the maximum depth of the organizational tree. 

- The org chart can be of any size.

- The org chart is represented as a Python list (more below). 

- You are given one class and one function to start.

class EmployeeNode

- This class defines a node in the organizational tree. Each node represents an employee's role (or name). The node can have two children: left and right, representing two direct reports of that employee. By default, these are set to None. Each node also has a value, which is the role (or name) of the employee.

build_org_chart()

- The purpose of this function is to build an organizational tree (binary tree) from a given list. Each item in the list is either a role of an employee or None (indicating an empty position). This function uses a queue to process each node in a level-order fashion. For every node, it will set its left and right children based on the next two values from the list. The function returns the root node of this tree.

Learner's Task

- Write a function - max_depth() - that calculates the maximum depth of a given organizational tree.

Example

- Given the list ["CEO", "CFO", None, "COO", None, None, "CTO"], the build_org_chart() function will build (a serialized version of) the tree below, and return 3 because the tree has 3 levels (i.e. a depth of 3).

>>> from org_chart import build_org_chart, max_depth
>>> org_list = ["CEO", "CFO", None, "COO", None, None, "CTO"]
>>> org_structure = build_org_chart(org_list)
>>> max_depth(org_structure)

See also the tests for more scenarios ...

Keep calm and code in Python!