# Code Challenge: Understanding Binary Tree Algorithms in Swift

Dec 27, 2019 · 4 min read

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   6Output: 15`

Example #2:

`Input: [-10,9,20,nil,nil,15,7]   -10   / \  9  20    /  \   15   7Output: 42`

## The Challenge

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

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 = 2let lindex = (2 * index) + 1 //left child indexlet rindex = (2 * index) + 2 //right child index//child nodes for "20"let left = sequence[lindex] //15let 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

`/* 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    }`

## Swift Algorithms & Data Structures

Modern Code, Illustrations & Computer science

Written by

## Wayne Bishop

I write about Swift Development & Computer Science. Get more tips on technical interview preparation at — www.waynewbishop.com

## Swift Algorithms & Data Structures

Modern code, Illustrations & Computer science

Written by

## Wayne Bishop

I write about Swift Development & Computer Science. Get more tips on technical interview preparation at — www.waynewbishop.com

## Swift Algorithms & Data Structures

Modern code, Illustrations & Computer science

## Multiple Skills? How LeWagon Could Help

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app