Login and get codingOf 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 itsrootat the top andleavesat the bottom.A tree consists of

nodesconnected byedges.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 aleaf.## Binary Trees

A

binary treeis 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 threeand consists of the following:-

O->rootnode with two children,1and2.-

1-> node with two children,3and4.-

3-> aleaf(node with no children)-

4-> leaf-

2-> child node of0with 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!

Metrics »

10 out of 14 users completed this Bite.

Will you be Pythonista #11 to crack this Bite?

Resolution time: ~41 min. (avg. submissions of 5-240 min.)

Pythonistas rate this Bite 3.67 on a 1-10 difficulty scale.

» You can do it! 😌

Ask for Help