# Code Challenge: Understanding Binary Tree Algorithms in Swift

For the past few months, I’ve been helping a student prepare for a technical interview at Facebook. Many aspects of the Facebook interview process are well-documented, however, this alone doesn’t guarantee success. As part of my weekly iOS Computer Science Lab, we also work on solving code challenges. Our latest topic included a review of understanding binary trees:

*Challenge**: Given a *non-empty* binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root:*

`Example #1:`

**Input: [4,5,6]**

4

/ \

5 6

Output: 15

*Example #2:*

**Input: [-10,9,20,nil,nil,15,7]**

-10

/ \

9 **20**

/ \

**15** **7**

Output: 42

## The Challenge

As the name indicates, a binary tree is a popular type of tree-based data structure. To support their time and space efficiencies, trees are often represented by a key and two or more **leaf nodes**, similar to the following structures:

As one may guess, **recursion** is also a common property of tree-based structures. Even though most recursive functions are frowned upon in real applications, trees allow for certain efficiencies as each leaf-node can also represent another tree:

If not understood correctly, trees can lead to confusion as well as added complexity. To solve our code challenge, we’ll need to devise a consistent method for navigating our tree and a way to compare all possible permutations.

# Traversing The Tree

Let’s work through visualizing our ideas before committing them to code. To start, we’ll first address how to navigate the tree. Since tree-based structures incorporate an additional concept property of *depth*, simple techniques like fast-enumeration aren’t normally applied. Instead, we can use specific traversal algorithms like **depth or breadth-first search** (e.g. DFS and BFS respectively). Even though the topic of BFS is detailed enough for a new discussion, we can conclude this would be the normal way one would traverse such a structure. However, since we are working with a Binary Tree, we can apply specific algorithmic efficiencies to help **shortcut** the traversal process.

So, what is a Binary Tree? Essentially, it is a standard Array that is **visualized** as a tree. In this case, emphasis is placed on the visualization aspects since this will affect how we navigate the structure. For example, for each node, its left and right leaf child nodes can actually be **calculated** using these simple formulas:

`let sequence = [-10,9,20,0,0,15,7]`

let **index**: Int = 2

let **lindex** = (2 * index) + 1 //left child index

let **rindex** = (2 * index) + 2 //right child index

//child nodes for "20"

let left = sequence[**lindex**] //15

let right = sequence[**rindex**] //7

As discussed, these formulas work because the underlying structure for our Tree is an **Array**. This differs from other structures like a B-tree, Trie or Graph where one would apply a specific custom data structure to represent a model.

# Making Comparisons

Since our Binary Tree is actually nothing more than an Array, we can indeed use basic enumeration to iterate through all values. However, we’ll apply our formulas to determine our child leaf nodes. Once established, we can track the totals of each sub-tree using a simple form of memoization (eg. **dynamic programming**).

`/*`

**challenge**: given a non-empty binary tree, find the maximum path sum.

*/

let sequence = [-10,9,20,0,0,15,7]

func maxPathSum() -> Int {

var max: Int = 0

//iterate through each node in the array

for (pindex, element) in sequence.enumerated() {

//determine child indicies

let lindex = (2 * pindex) + 1

let rindex = (2 * pindex) + 2

var left: Int = 0

var right: Int = 0

if sequence.indices.contains(lindex) {

left = sequence[lindex]

}

if sequence.indices.contains(rindex) {

right = sequence[rindex]

}

//calcuate subtree value

let total = element + left + right

//compare the subtree totals

if total > max {

max = total

}

}

return max

}