## Organizational chart

Level: Advanced (score: 4)

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!