Intro

A tree is a data structure that consists of nodes, with values and pointers to child nodes, which recursively form subtrees. Lets understand the structure of a Tree. Trees have a root node, and each node has 0 or more child nodes. Trees cannot contain cycles -- that is, Trees are top down and a node cannot reference anything above itself. Typically, tree questions are riddled with ambiguity and incorrect assumptions. Be careful! Always clarify with your interviewer all the details of the question.

The path from the root node to the leaf node is known as a 'branch'. A trees height, is the length of its longest branch. The depth of a tree, is the distance of root to node level.

You can think of trees like graphs that are acyclic, connected, directed, with an explicit root node, and all nodes have a single parent.

Types of Trees

• Binary Tree
  • A binary tree is when each node has up to 2 children nodes. Not all trees are considered Binary trees
  • A node is called a "leaf" when it has no children nodes attached to itself

• Binary Search Tree
  • A binary search tree is when every node fits into an ordering system. When all left descendants ≤ the current node value ≤ all right descendants
  • Some binary search trees may or may not have duplicate values. Clarify this!

• Balanced Tree
  • A balanced tree is when left and right subtrees are the same size

• Complete Binary Tree
  • A complete binary tree is when every level of the tree is filled from left to right

• Full Binary Tree
  • A full binary tree is when every node has 0 or 2 children -- aka there are no nodes with only 1 child node

• Perfect Binary Tree
  • A perfect binary tree is when the tree is both full and complete. All leaf nodes are at the same level, and this level has the maximum amount of nodes
  • Perfect trees have 2ᵏ-1 nodes, where k is the number of levels in a tree
  • Never assume a tree is perfect in an interview!

Binary Tree Traversals

There are 3 main methods of traversing a binary tree: in-order traversal, pre-order traversal, and post-order traversal. In a pre-order traversal, we arrive at the root node first, then traverse the left side, then the right side. In post-order traversal, we traverse the left side, then the right side, then the root node. And finally in in-order traversal we traverse the left side, then the root node, then the right side. An easy way to think of these is the in reference to the root node. The order in which we traverse depends on when we visit the root node. For example, post-order traversal has us visit the root node last (or post-everything else).

Binary Heaps

A min heap is a complete binary tree, where each node is smaller than its children. The root node is the minimum of the entire structure. A max heap is the same rules but vice versa -- the root node is the maximum & nodes are larger than its children.

We should take a look at some operations on a min/max heap:

• When we insert into a heap, we insert the new value at the bottom - right most spot to maintain the completeness of the tree. Then we will fix the tree by swapping the new element with its parent until we find the correct spot. All-in-all this will take O(logN) time.
• Extracting the min/max element is easy. We remove the root node, and swap with the last element. Then we bubble down the new element until it is in place. Swap as we go down. All-in-all this will take O(logN) time.

Tries

Tries (or prefix tree) is a variant of a n-ary tree in which characters are stored at each node. Each path down the tree represents a word. Tries are most commonly used to store entire english language for quick prefix lookups. Hash Tables are fast, but cannot tell us valid prefixes of words.

Invert Binary Tree

The worlds most popular tree problem!! Time to dive in.

So as you will find with most Tree problems, we can solve this recursively or iteratively. Lets go over both, but keep in mind! We lose some space efficiency when we go with a recursive solution.

[ Recursive ]

[ O(n) worst time + O(n) space ]

So at first glance, the recursive solution would actually be pretty easy. When I solve recursive problems, I start at the base case, and build out from there. In this problem, our base case is if the root node is nil, we should return nil in our function. Another base case is if the root has no children, we just return the root. After that, it is about swapping the left and right side.

if input is nil return nil
swap left and right of the root
return the root

As we discussed earlier, the space complexity here, is O(n) where n is the number of nodes in the call stack. We know at every level, we will need to recurse the left and right nodes to swap them. The time complexity here is O(k) where K represents the number of nodes in the tree. We know we need to swap all of them at least once.


The final code is pretty simple:

if root == nil { return nil }
let left = invertTree(root?.left)
let right = invertTree(root?.right)
root?.left = right
root?.right = left
return root

[ Iterative with a Queue (BFS) ]

[ O(n) worst time + O(n) space ]

We can use Breadth-First search for an iterative solution. In Swift, a Queue is really just an array, where we utilize the removeFirst() function on sequences to simulate array removal. First we want to add the root node to our array. While our queue is not empty, its safe to assume we have more nodes to visit, and to invert. At every step, we will remove the first element from our queue, and invert it. It follows very similar logic to our recursive solution, we just have another data structure involved.

create a queue
add root to queue
while queue is not empty
    pop first element in queue
    invert left and right 
    add left and right to the queue

The time complexity here once again is O(N) because we need to visit every node to invert it. Our space complexity is lightened due to the lack of recursive call stack, but we lose that efficiency by introducing a Queue that grows with every node we have added to it. This on average comes out to be O(n) as well.

Here is the final implementation:

guard let root = root else { return nil }
var queue = [TreeNode?]()
queue.append(root)

while !queue.isEmpty {
    let node = queue.removeFirst()
    if node == nil { continue }
    let left = node?.left
    let right = node?.right
    node?.left = right
    node?.right = left
    
    queue.append(node?.left)
    queue.append(node?.right)
}

return root

Maximum Depth of Binary Tree

Building upon our previous knowledge, we are presented with the following:

Not too bad! This too, can be solved iteratively or recursively.

[ Recursive ]

[ O(n) time + O(n) space ]

The idea behind the recursive solution, is very similar to the "Invert Binary Tree" problem we saw earlier. We want to traverse every node, and at each level, we want to keep track of the depth at any given moment. For example, if we have a tree with 1 parent node and 2 children nodes, the maximum depth will be whichever side (left or right) has a larger depth.

Solving for the base case first, the base case is if the root node is nil, we return a depth of 0. Ultimately we want to append 1 to every level node we are at, and append 1 to the current depth. Something like this:

if root is nil return 0
get depth of left, recursively
get depth of right, recursively 
get the max of left vs right
return 1 + the maximum side

The time complexity here is pretty simple. We traverse all nodes, both left and right. So the time complexity is O(n) where n is the number of nodes in the tree. The space complexity would be constant, except we need to keep track of the call stack for all the recursive calls. So in this case the space complexity is O(n) where n is the number of nodes in the call stack.

The real implementation is pretty simple, like so:

if root == nil { return 0 }
let left = maxDepth(root?.left)
let right = maxDepth(root?.right)
let maxi = max(left, right)
return 1 + maxi 

But now for the real test...the iterative solution!

[ Iterative with a Stack (BFS) ]

[ O(n) worst time + O(n) space ]

This is very similar to the invert binary tree problem, except our queue structure will be a little different. We want to, at each queue node, hold the depth of our tree node & the node itself. For example, if I have a tree with a root node of (3), our queue will hold this node as a tuple of (3, 1) where 1 is the depth of the node at the given time. Other than that, we essentially have the same problem as the invert binary tree.

create a queue of tuples
append the root to the queue
while the queue is not empty
    remove first node item from the queue
    update global max from our queue value
    if there is a left value for our queue node
        add the left to the queue and append the depth by 1
    if there is a right value for our queue node
        add the right to the queue and append the depth by 1
        
return the global max

Nothing much has changed here in terms of time complexity, as we still need to visit every single node in the tree. This comes out to O(n) time, and meanwhile our space complexity is lightened due to the lack of recursive call stack, but we lose that efficiency by introducing a Queue that grows with every node we have added to it. This on average comes out to be O(n) as well.

guard let root = root else { return 0 }
var queue = [(TreeNode?, Int)]()
var globalMax = 0
queue.append((root, 1))

while !queue.isEmpty {
    let (node, depth) = queue.removeFirst()
    globalMax = max(globalMax, depth)
    if let left = node?.left { queue.append((left, depth + 1)) }
    if let right = node?.right { queue.append((right, depth + 1)) }
}

return globalMax

Woohoo!

Same Tree

Building upon our previous knowledge, we are presented with the following:

And you probably guessed it! We need to traverse our 2 input trees similar to the other problems. We can go about this recursively with DFS or using BFS and a queue

[ Recursive ]

[ O(n) time + O(n) space ]

So the trick here is, if we go with a recursive solution, we need to cover all base cases. Since there are 2 trees, and every node on the tree has a chance to be nullable, we need to really think about this.

The base cases that come to mind, are:

1. If both of the root nodes are null, return true as they are equal
2. If ONE of the root nodes is null, return false, as one is null and one is not, representing inequality
3. If the values of the nodes is not equal, then return false, as the nodes are not the same.

Other than that, it is business as usual! We need to recurse left, and recurse right. As long as the left and right subtrees are equal, we have the same tree!

if both p and q are null return true
if either p or q is null return false
if p value does not equal q value return false 

recurse left
recurse right

if left is valid AND right is valid, return true

The time complexity here is pretty simple: O(n) where n is equal to the number of nodes in the larger tree. We will need to visit every node in both so our time is limited to the larger tree. The space complexity here is O(n) where...you guessed it...n is equal to the recursive call stack! Same as the others.

Final product is like so:

if p == nil && q == nil { return true } // if both are nil 
if p == nil || q == nil { return false } // if one is nil
if p!.val != q!.val { return false } // not equal values
let isLeftValid = isSameTree(p!.left, q!.left) // recurse left
let isRightValid = isSameTree(p!.right, q!.right) // recurse right
return isLeftValid && isRightValid // return left and right are simultaneously valid 

[ Iterative with a Queue (BFS) ]

[ O(n) time + O(n) space ]

So just like our other problems, to eliminate recursion we can introduce a new data structure to traverse the tree. We still need to keep our base cases in check though, as when we remove elements from the queue, we will make sure they follow our earlier rules

add p and q to the queue
while the queue is not empty 
    remove first from queue representing p
    remove first from queue representing q
    check our bases cases:
        if the values are not equal, or only ONE is nil return false
    add left and right of each to the queue

The time complexity is O(n) where n is equal to the number of nodes in the larger tree. We stil need to visit every node in both trees so the time is constrained to the larger tree. And the introduction of the queue keeps our space complexity here at O(n) where n is the number of nodes in the queue at any given time. For the final implementation:

var p = p
var q = q
var queue = [p ,q]

while !queue.isEmpty {
    p = queue.removeFirst()
    q = queue.removeFirst()
    if p == nil && q == nil {continue}
    if p == nil || q == nil {return false}
    if p!.val != q!.val {return false}
    queue.append(p!.left)
    queue.append(q!.left)
    queue.append(p!.right)
    queue.append(q!.right)
}
return true

Subtree of Another Tree

Time to continue our tree journey with another example!

Just like every other problem we have encountered, we can solve this recursively or iteratively using BFS/DFS!

[ Recursive ]

[ O(n · m) time + O(n + m) space ]

To make this problem a little easier, we can break out the "is same tree" functionality into its own function. This makes it unit testable, as well as easier to read from a code perspective. Once we break out this out into another function, it makes our problem much easier. We can traverse our root tree using DFS & if our current root at a given time is equal to the subroot, we can return true. Since this is a recursive function, if somewhere on the left or right of our tree, we have a subtree, we can return true.

if root is nil return false
is current root & subroot are the same return true
recurse left
recurse right
return left OR right true

The time complexity for our solution here is a little complex. Checking if a root & subroot are the same tree, requires us to traverse every node of our subtree & root tree. This is M · N where M is the number of nodes in the root tree, and N is the number of nodes in the subtree. We need to traverse our entire tree M, and at every step we traverse our N subtree looking for a similarity. This comes out to O(M·N) time complexity. The space complexity here is O(n + m) where N is the number of calls in the stack for traversing our root node in a dfs fashion. At every recursive call, we call our "is same tree" function, so M is representative of the number of "is same tree" function calls in the stack. This evens out to O(n + m) space.

The final implementation comes out to the following:

func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
    return dfs(root, subRoot)
}

func dfs(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
    if root == nil { return false }
    if isSameTree(root, subRoot) { return true }
    let left = dfs(root?.left, subRoot)
    let right = dfs(root?.right, subRoot)
    return left || right
}

func isSameTree(_ one: TreeNode?, _ two: TreeNode?) -> Bool {
    if one == nil && two == nil { return true }
    if one == nil || two == nil { return false }
    if one?.val != two?.val { return false }
    let isLeftValid = isSameTree(one?.left, two?.left)
    let isRightValid = isSameTree(one?.right, two?.right)
    return isLeftValid && isRightValid
}

[ Iterative with a Queue (BFS) ]

[ O(n + m) time + O(n + m) space ]

The idea here is the exact same as other iterative BFS problems. We need to use a queue and pop nodes off of the queue to perform our checking logic.

add root and subroot to the queue
while the queue is not empty 
    remove first from queue representing root
    remove first from queue representing subroot
    if root and subroot are same tree return true
    add left and right of each to the queue
return false

Space complexity as we know is O(n + m). N is representative of the space of our queue at any given moment, where m is the number of "is same tree" function calls. Time complexity is once again, O(n + m) for the reasons stated above.

Here is the final implementation:

func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
    return bfs(root, subRoot)
}

func bfs(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
    guard let root = root else { return false }
    var queue = [TreeNode?]()
    queue.append(root)

    while !queue.isEmpty {
        let node = queue.removeFirst()
        if node == nil { continue }
        if isSameTree(node, subRoot) { return true }
        queue.append(node?.left)
        queue.append(node?.right)
    }
    return false
}

func isSameTree(_ one: TreeNode?, _ two: TreeNode?) -> Bool {
    if one == nil && two == nil { return true }
    if one == nil || two == nil { return false }
    if one?.val != two?.val { return false }
    let isLeftValid = isSameTree(one?.left, two?.left)
    let isRightValid = isSameTree(one?.right, two?.right)
    return isLeftValid && isRightValid
}

Lowest Common Ancestor of a Binary Search Tree

Turn up the heat a little!

To start here we should revisit the definition of a Binary Search Tree..."A binary search tree is when every node fits into an ordering system. When all left descendants ≤ the current node value ≤ all right descendants". When you see a BST being stated in the problem statement, we should know to use the BST characteristics to our advantage. We should immediately think to compare the children node values to the root value, and vice versa.

[ Recursive ]

[ O(n) time + O(n) space ]

For our problem at hand we should check P and Qs value relative to the root. If both P and Q are greater than the root, we should repeat our search in the right half of the tree. If both P and Q are less than the root, we should repeat our search in the left half of the tree. And if neither of those cases are true, we should return our root node, because we cannot go any deeper in the tree.

This is fairly straight forward, but what about the edge cases where either P or Q is equal to the root node? Well this should not change much in our case. This is because since either P or Q is equal to the root, we know neither the left or right subtrees would contain the value we are searching for.

Here is a high level implementation:

if P and Q are greater than root
    search right subtree
if P and Q are less than root
    search left subtree
else
    return root

The space complexity here is O(n) where N is the number of recursive calls on the call stack at any given time, this should be roughly equal to the height of the Tree. The time complexity is roughly equal to the number of nodes in the tree, and this is because at the worst case, we need to traverse down to the bottom of the entire tree through every node...O(n). This time complexity assumes the tree is not balanced.

The final implementation is as follows:

guard let root = root, let p = p, let q = q else { return nil }
if root.val < p.val && root.val < q.val { // search right
    return lowestCommonAncestor(root.right, p, q)
} else if root.val > p.val && root.val > q.val { // search left
    return lowestCommonAncestor(root.left, p, q)
} else {
    return root
}

[ Iterative ]

[ O(n) time + O(n) space ]

The iterative solution follows the same pattern as the recursive, without the recursion.

keep a current node to traverse the tree
while the current is not nil
    if P and Q are greater than root
        assign current to right node
    if P and Q are less than root
        assign current to left node
    else
        return root
return current

The space complexity here is obviously improved without the recursion. This equates out to O(1) space. The time complexity is O(n) because we need to possibly traverse every node in the entire tree. If the tree is balanced though this would be an O(logN) time complexity.

guard let root = root, let first = p, let second = q else { return nil }
var current: TreeNode? = root
while let node = current {
    if node.val < first.val && node.val < second.val {
        current = node.right
    } else if node.val > first.val && node.val > second.val {
        current = node.left
    } else {
        return current
    }
}
return current

Keep it rolling!

Binary Tree Level Order Traversal

Lets take a peek at the next tree challenge

If this problem looks familiar...its because it is! We have had some tree problems in the past where we traverse the tree with BFS (Breadth First Search). And this problem is eerily similar! We just have a slight wrinkle on what we should be doing at any given tree level.

[ BFS with Extra Loop ]

[ O(n) time + O(n) space ]

The idea here is, we use a queue like we would any other BFS tree traversal. But the difference is, while our queue is not empty, we want to keep a count of how big our queue is. While the queue has a count greater than or equal to zero, we want to pop values, and add child values to the queue. After we have popped values from the queue all the way until the queue is empty, we know we have traversed a level, and we can add the traversed values to our return array.

It is important to emphasize, the trick here is keep tracking of how big the queue is at every level, with its own variable.

We should note that the problem is asking for a LEVEL order traversal, aka root, left, and then right.

create queue
add root to queue

while queue is not empty
    get length of current queue
    create an array to track this level
    for element in length of queue
        remove first value from queue
        add value to this level array
        add left child to queue
        add right child to queue
    add this level array to return value
    
return nested array we created

The space complexity here is O(n) because of the queue data structure we are using. In a Binary tree we can have at most O(₁/₂n) values on it at any given time. The time complexity here is O(n) because we will only ever visit each node one time.

Here is the final implementation!

guard let root = root else { return [] }

var result = [[Int]]()
var queue: [TreeNode?] = [root]

while !queue.isEmpty {
    var count = queue.count - 1
    var currentIterativeArray = [Int]()
     while count >= 0 {
       if let node = queue.removeFirst() {
           currentIterativeArray.append(node.val)
           count -= 1
           if let left = node.left { queue.append(left) }
           if let right = node.right { queue.append(right) }
       }
    }
    result.append(currentIterativeArray)
}
return result

Like I said in the beginning, it is a pretty straight forward BFS with a little wrinkle!

Validate Binary Search Tree

Now this one is a little tricky...

Lets make sure we are reading the problem correctly! The first thing to call out is the definition of a BST. The left subtree of a node must be less than the root node. NOT less than or equal to, only less than. Same thing with the right side, the right subtree must be greater than the node. Also, pay attention to the wording, if a node is on the left side of the top most root, it must be less than the value of the root. It does not matter if the node is 4 levels down from the top. If it is on the left side of the tree, then we should ensure its value is less than the root node value.

[ DFS with Comparison ]

[ O(n) time + O(n) space ]

So typically when validating a binary tree we would use DFS. But this time its a little different, and that is because of the BST definition, we can compare a roots value to its left and right value, but that does not help us as we get further and further down the tree. We lose track of the root node value.

So the trick here is to recognize what we are doing at each node and each level. Say we have a tree with a topmost root node value of 5. We know for this to be valid, 5 must be less than -∞ and greater than ∞. Next lets say the topmost node value of 5, has a left side child of 3. For this 3 to be a valid node, we know 3 must be less than -∞ BUT greater than 5. Consider 5 has a right child node of 7. 7 must be greater than 5, but less than ∞.

The point here being, we need to make a comparison at each node. When we recursively travel through our tree, we need to just send the comparison values down the call stack. When recursing left, we know the minimum should be the current minimum, but the maximum should be the root node value (parent). Vice versa with the right side. Something like this:

if node is nil return true
if our node is greater than the minimum value, or, the node is less than the maximum value
    return false
return left and right subtrees are valid, while passing the new min & max values

The time complexity here is pretty straightforward as we need to visit every node here once. The comparison itself is constant time, but the time comes out to O(n) where n is the number of nodes in the tree. The space complexity here as we have seen is O(n), due to the recursive nature of the solution. We need to host at most n number of recursive calls when we traverse the tree. N in this case stands for the height of the tree, which evens out to O(n) time.

The final implementation is as follows:

func isValidBST(_ root: TreeNode?) -> Bool {
    return isBst(root, min: Int.min, max: Int.max)
}

private func isBst(_ root: TreeNode?, min: Int, max: Int) -> Bool {
    guard let root = root else { return true }
    if root.val <= min || root.val >= max { return false }
    return isBst(root.left, min: min, max: root.val) && isBst(root.right, min: root.val, max: max)
}

We just need to be careful on this one! Do not blindly implement DFS, make sure we are understanding the problem.

Kth Smallest Element in a BST

Keep chugging along!

So here we have another BST problem. We should make sure we remember that a BST is a tree where all elements on the left side of the tree are less than the root, and all elements in the right subtree are greater than the root. Also we should remember how we normally traverse trees in general, here we will be using DFS.

[ DFS inorder traversal ]

[ O(n) time + O(n) space ]

So we should consider the smart way to go about this. If we remember, Inorder traversal is when we visit the entire left side, then the root, then the right subtree. If we do an Inorder traversal on a BST, and we store the elements in an array as we visit them, we will end up with an array of all the nodes in order from smallest to largest!

This will make our lives a lot easier, if we want to find the kth-smallest element (1 indexed) we can then just return the kth - 1 element in our array we have created.

build our list
return the k-1 element of the list


build list function:
    if root is nil, return empty array
    add root value to new list
    recurse left and get left array
    recurse right and get right array
    return left array + root array + right array

The time complexity here is O(n) where n is the number of nodes in the tree, we need to visit every node once to build the array. Arrays offer constant time lookup when accessing a value, so we can ignore the time complexity there. The space complexity is O(n) because we are building an array where the size of the array is how many nodes are in the tree. We are also recursively traversing the tree, so we need O(n) at most calls in the recursive call stack. This will even out to O(n) on average.

Here is the final implementation!

func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
    guard let root = root else { return 0 }
    var list = buildList(root)
    return list[k - 1] 
}

func buildList(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    var list = [root.val]
    let left = buildList(root.left)
    let right = buildList(root.right)
    return left + list + right
}

Easy!

[ BFS with a Stack ]

[ O(n) time + O(n) space ]

I think it would also be intelligent here to mention, we do not always have to traverse the tree using DFS, we can of course use BFS with a Stack like structure. It carries very similar logic to our DFS logic, but we save ourselves from the recursion. We will go as far left in our tree as possible and find the smallest value. After that, we will pop the parent and traverse right. All the while we need to keep a count of the values rankings. Every time we pop a value from the stack, we can decrement our K value count.

func iterativeStack(_ root: TreeNode?, _ k: Int) -> Int {
    var stack = [TreeNode]()
    var count = k
    var root = root
    
    // Go as far left as we can
    while root != nil {
        stack.append(root!)
        root = root?.left
    }
    while count != 0 {
        let node = stack.removeLast()
        count -= 1
        if count == 0 { // When our K value count is now at 0, we know we have found the right value. 
            return node.val
        }
        var rightNode = node.right
        while rightNode != nil {
            stack.append(rightNode!)
            rightNode = rightNode?.left
        }
    }
    return -1
}

Nice!

Construct Binary Tree from Preorder and Inorder Traversal

Hope you remembered how to traverse a tree! This one is all about testing your inner tree knowledge.

In concept this is a straight forward problem, it just takes a little creativity arriving at the solution. We will be using DFS for this problem, which means recursion.

[ DFS recursive build ]

[ O(n) time + O(n) space ]

Lets think about what preorder traversal means. Preorder traversal is arriving at the root first, then left subtree, then right subtree. This means in our example problem, our preorder array is [3,9,20,15,7], and the first element of this array is 3. Thus we know our root of our entire tree is 3. Cool. Now what?

Now lets think about inorder traversal. Inorder traversal is arriving at the left node first, then the root node, then the right now. So taking what we know from preorder traversal, we know our root is 3. If we find the value of 3 in our inorder traversal array, we can partition the array to know which values are in the left and right subtrees. For example, our inorder array is [9,3,15,20,7]. By finding the root value of 3, we can split our array up into 2 parts. We now know that the left subtree consists of [9]. While the right subtree consists of [15, 20, 7]. What next?

This pivot point I will refer to as "Mid". In our above example, our midpoint is 3. There is a "gotcha" to this problem as well. We should be careful when there is no left subtree to populate, that is when we should move on to the right subtree. If this midpoint has an index of 0, its time to move on to the right side. Lets see an example. If our preorder array is [7, 10]. And our inorder array is [7, 10]. Our midpoint here would be 7. We can see our midpoint in our inorder array has a midpoint of 0. This is because there is nothing to add to the left subtree and we should move on!

We can recursively repeat this process for our left and right subtrees, excluding values we do not need. So to find the right subtree for 3 for example, our preorder array would be [20, 15, 7]. Our inorder array will be [15, 20, 7]. Rinse and repeat!

if either inorder or preorder is empty, return nil (base case)

create root node from preorder arrays first value
find midpoint in inorder array

find left of root by recursing left subtree
find right of root by recursing right subtree

return root

Given this is a recursive solution, the space complexity here is O(n) where n is the height of the call stack at any given time. The time complexity here is O(n) worst case, where the biggest time constraint is finding the midpoint in the inorder array. We may have to search the entire array to find it. Time to implement!

if preorder.isEmpty || inorder.isEmpty { return nil }
var rootNode =  TreeNode(preorder[0])
if let mid = inorder.firstIndex(of: rootNode.val) {
    if mid > 0 { // if we have a left side to populate
        let leftPreorder = Array(preorder[1...mid])
        let leftInorder = Array(inorder[0..<mid])
        rootNode.left = buildTree(leftPreorder, leftInorder)
    }
    let rightPreorder = Array(preorder[mid + 1..<preorder.count])
    print(rightPreorder)
    let rightInorder = Array(inorder[mid + 1..<inorder.count])
                print(rightInorder)

    rootNode.right = buildTree(rightPreorder, rightInorder)
}
return rootNode

Almost done!

Binary Tree Maximum Path Sum

And now we enter the hard realm 👀

This is an decently solvable hard leetcode problem, we just need to remember our tree fundamentals when it comes to DFS.

[ DFS recursion w/ optimization ]

[ O(n) time + O(n) space ]

I think for this problem, understanding what the problem is asking is of the most importance. A path, in this case, is the ability to split the path of a node only once. And by this I mean, say we have a tree with a root of 1, and children of 2 and 3. We can only split our path once at the topmost root node of 1. We cannot say, go from 1 to 2, then back to 1, then to 3. We only split once. In the case where we are in a subtree and we have already split, we should be choosing the left or right path that is greater.

Also, some of the nodes may be negative. So this should affect the decision we are making when its time to choose a path. If we have to split between left and right, and one direction gives us a negative value, we should avoid it. It is possible negative values are a part of our path, we should just be methodical about when to use them.

So lets think about how we would go about solving this. I think at first it should be pretty clear that we will be recursively using DFS to eliminate repeated work. We want to, at each node in our tree, figure out if splitting at the current node and combining the left and right subtrees is greater, or if we have already split what is the maximum path using either the left OR right subtree.

Thinking recursively lets start with a base case. If the root of our tree is nil, we should return a max path of zero. Easy. We will then recurse left and right. We need to determine if the left max path is less than 0. If it is, we should not use this value as it will not optimize our path. Nice.

For this problem, we should be keeping a global max path variable, this keeps our code clean when determining the max path of the entire structure. At every iteration we should determine which is bigger: the current global max path sum, or splitting at the current node. Splitting at the current node can be represented as root + left max + right max.

Now lets assume we have already split earlier in our traversal, and we are deep into our tree structure. In this case, for our subtree we should just be returning what the maximum unidirectional path is to our parent. In this case we will just add the root to the maximum of the left vs right subtrees. Slightly different. Recapping all of that, some pseudocode looks like this:

if root is nil return 0

keep global max path sum, starting value is our root value


get left value by recursing
get right value by recursing
if left value is less than zero, use 0 instead
if right value is less than zero, use 0 instead

update global max with whichever is greater: the global max, or if we split at this present node. root + left + right

return to our parent, assuming we already split. root + max of left vs right

Due to the recursion, the space complexity here is O(n) where n represents the maximum size of the call stack at any given time. This is also equal to the height of the tree. If it is a balanced tree then the space complexity is O(logn). The time complexity here is O(n) because we need to visit every node in the tree only once.

And finally here is the implementation:

var result = root!.val

func recurse(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    let left = recurse(root.left)
    let right = recurse(root.right)
    let leftMax = max(left, 0)
    let rightMax = max(right, 0)
    result = max(result, root.val + leftMax + rightMax)
    return root.val + max(leftMax, rightMax)
}
recurse(root)
return result
}

Only one more to go!

Serialize and Deserialize Binary Tree

and here we are, the final problem in our tree journey. Lets dive in!

I think to start, we need to break this problem down into 2 parts, the serialization and the deserialization. And, as with most tree problems, we can use either BFS or DFS to solve this. I will be going over both for posterity 😎

No matter if you use BFS or DFS, the idea behind a solution is the same. We know to serialize we want to make the tree into a string. Lets say we have a tree where the root is 1, and it has children of 2 & 3. If we use DFS, the string will be "1, 2, nil, nil, 3, nil, nil". We will want to add all children of nodes, even if they are nil. We want to also add the differentiator between nil and non nil nodes. This is because we need to know in DFS when to move on from the left subtree and go to the right subtree. In this case we used "nil" but you can use anything you want like "null", "next" or even "🔥". We also want to comma separate our values so we know if a value in the string is "12" meaning 1 node of value 12, or 2 values with the values of "1" & "2".

Using this same logic our string for a BFS solution would be "1, 2, 3, nil, nil, nil, nil", due to the nature of BFS we are looking at the tree on a level by level basis.

Serialization

[ DFS recursive string creation ]

[ O(n) time + O(n) space ]

For DFS, we know we will be recursively traveling down the tree until we reach our base case to end our recursion. We will also be traveling the left and right subtrees from our root. This solution is pretty straight forward. If we find a nil root, we will be adding "nil" to our string. Else we need to add subtree strings to our root.

keep a global return string

if root is nil 
    return string += "nil,"
    break from recursion
return string += root value + ","
return string += left subtree recursed
return string += right subtree recursed

Space complexity here is O(n) where n is the height of the tree, and the max size of the call stack at any given time. We have to visit every node and at each iteration we are doing constant addition, so the time complexity is O(n) where n is the# of nodes in a tree.

Something like this:

var result = ""

guard let root = root else {
    result += "null,"
    return 
}
result += "\(root.val),"
result += serialize(root.left)
result += serialize(root.right)

return result

[ BFS Queue string creation ]

[ O(n) time + O(n) space ]

As is usually the case with BFS, its a little more complicated due to the use of a Queue, but still not too bad. Here we will be keeping an array of values, and at the end, manually do the comma separation. This is just to give a different look at the problem.

First we will add the root of our tree to the queue. Then while the queue is not empty, we will add non nil values to our values array. If we find a nil value, we will add "nil" to our values array. For every node we pop we will add its children to the queue regardless of optionality. Like this:

keep a queue
keep a list of values

while queue is not empty
    pop first from queue
    add node to values array
    add left child to queue
    add right child to queue
    if node is nil add "nil" to values array
    
return values array, but comma separated

Space complexity here is O(2n) which evens out to O(n) due to the queue we need to keep track of our nodes. We will always add nodes to our queue for every node (and child node) we have. This evens out to O(n) time complexity.

Here is the final implementation:

var vals = [String]()
var queue: [TreeNode?] = [root]

while !queue.isEmpty {
    if let node = queue.removeFirst() {
        vals.append("\(node.val)")
        queue.append(node.left)
        queue.append(node.right)
    } else {
        vals.append("nil")
    }
}
return vals.joined(separator: ",")

Ok we are serialized and good to go!

Deserialization

[ DFS recursive ]

[ O(n) time + O(n) space ]

The idea here is the same with serializing DFS. But we just want to be careful when we approach a nil value. A simple way to get around this is using Swifts Int initializer. If we pass "2" into the initializer, Swift will give us 2. If we try to pass "nil", the initializer will conveniently fail.

separate our string into a comma separated array

pop the first from the array
try to convert the value into an Int
    if it fails, return nil

create a new root node
node.left is equal to the recursive left subtree
node.right is equal to the recursive right subtree
return new root node

Same as always, space is the call stack size O(n). Time complexity is O(n) which is roughly the number of nodes in the tree. This is how we would go about DFS deserialization:

let val = nodes.removeFirst()
guard let valInt = Int(val) else { return nil }

let node = TreeNode(valInt)
node.left = deseralize_DFS(&nodes)
node.right = deseralize_DFS(&nodes)
return node

[ BFS queue ]

[ O(n) time + O(n) space ]

This one is a bit more complicated, by using BFS deserialization. Like DFS, we will want to convert our string into a comma separated array. We should attempt to keep a pointer in our array, so we know where in our values we are iteration on. Per usual we will create a queue and add our root to it. While the queue is not empty, we will pop nodes from the queue. BUT after we pop, we need to look at our values array. If the value is not nil only then will we add the left child node to our queue. Same with the right side. Every time we check the values array we want to move our pointer by 1 spot.

separate string into comma separated array
create queue with a new root node we create

while the queue is not empty
    remove queue from node
    if values pointer is not a nil value
        node.left is a newly created node from values array
        add this new node to the queue
    move values pointer by 1
    if values pointer is not a nil value
        node.right is a newly created node from values array
        add this new node to the queue
    move values pointer by 1

return new root

Space complexity here is O(n) due to the queue we need to keep track of our nodes. We will always add nodes to our queue for every node (and child node) we have. This evens out to O(n) time complexity. Value comparison and assignment is always constant time.

guard data != "nil" else { return nil }
let vals = data
    .split(separator: ",")
    .map { String($0) }
let root = TreeNode(Int(vals[0])!)
var queue = [root]

var idx = 1
while !queue.isEmpty {
    let node = queue.removeFirst()
    if vals[idx] != "nil" {
        node.left = TreeNode(Int(vals[idx])!)
        queue.append(node.left!)
    }
    idx += 1
    if vals[idx] != "nil" {
        node.right = TreeNode(Int(vals[idx])!)
        queue.append(node.right!)
    }
    idx += 1
}
return root

Well done!!!! Trees problems should be a breeze now!!