Code Challenge: Understanding Binary Tree Algorithms in Swift

Wayne Bishop
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 6

Output: 15

Example #2:


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

-10
/ \
9 20
/ \
15 7

Output: 42

The Challenge

Binary Search Tree
Trie Data Structure

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:

Binary Tree: The highlighted element acts as a child leaf node as well as a root node.

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 = 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

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

Wayne Bishop

Written by

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

Wayne Bishop

Written by

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

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

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store