A pattern to solve Binary Tree problems with Golang

I was reviewing some binary tree concepts when YouTube recommended this amazing video from the Inside code channel. In a nutshell, this video shows how the simple recursive definition of a binary tree can be used to solve a lot of binary tree problems in code interviews. So, I decided to write this article, summarizing the idea and applying it to real-life solving some questions from LeetCode and GeeksForGeeks using Golang.

The simple recursive definition of a binary tree

As I pointed out before, the recursive definition of a binary tree is enough to turn us able to solve a huge amount of code interview questions. Thus, let's look at this definition.

The recursive definition of a binary tree accordingly with Stanford CS Education Library is:

"[...] a binary tree is either empty (represented by a null pointer) or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree."

In other words, a binary tree is made by:

• A root node
• A left node pointing to a subtree or a NULL pointer
• A right node pointing to a subtree or a NULL pointer

Where each "subtree" can be seen as binary trees (hence the recursive definition).

I tried to make a visualization of this in the figure below:

From a code perspective, we can write a BinaryTree data structure:

 type BinaryTree struct {
      Val int
      Left *BinaryTree
      Right *BinaryTree
 }

Okay, but how to use this to solve code interview problems? 🤔

A huge amount of code interview questions related to binary trees are to calculate some tree property or manipulate the tree in some specific way. Thus, we can approach these questions with the same logic of recursive definition of a binary tree, as shown below:

1. Calculate some property of a binary tree

1. Calculate the property for the root node
2. Recursively calculate the property for the tree at left
3. Recursively calculate the property for the tree at right
4. Merge those calculations and output the result

2. Manipulate a tree in some specific way

1. Manipulate the tree at left
2. Manipulate the tree at right
3. Attach root node to the manipulated right and left trees

It is yet a little abstract, right? So let's dive into some code questions to put this into practice.

Calculate maximum depth (or height) of a tree

LeetCode question
The tree depth is defined as the length from some source node to root node. Since on this question we are interested in the maximum depth, we want to calculate the depth from leaves to root node and select the maximum among them. This is exactly the definition of the height of a tree, which is the length of the longest path to a leaf node from the root node. We can rewrite this definition in the recursive form:

The height of a tree is 1 + maximum between the height of the left tree and the right tree.

Now, implement this is pretty straightforward:

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftMaxDepth := float64(maxDepth(root.Left))
    rightMaxDepth := float64(maxDepth(root.Right))
    return 1 + int(math.Max(leftMaxDepth, rightMaxDepth))
}

Reverse a binary tree

LeetCode question
Reverse a binary tree is a manipulation on a tree where all the nodes which were previously at the left of the tree go to the right of the tree and all the nodes from the right go to the left. The image below (from LeetCode question) makes it clearly:

We also can approach this recursively:

1. reverse the tree on the left
2. reverse the tree on the right
3. swap the left and right trees

The Golang code is showed bellow:

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    invertTree(root.Left)
    invertTree(root.Right)
    root.Left, root.Right = root.Right, root.Left
    return root
}

Get the maximum (or minimum) value in a tree

GeeksForGeeks question
The maximum value in a tree is simply the maximum between the value of the tree's root, the maximum of the left tree, and the maximum of the right tree. Once again, the recursive definition shows up.

import "math"

func maximumInTree(root *TreeNode) float64 {
    if root == nil {
        return math.Inf(-1)
    }
    maximumInLeft := maximumInTree(root.Left)
    maximumInRight := maximumInTree(root.Right)
    maximumInChildren := math.Max(maximumInLeft, maximumInRight)
    return math.Max(maximumInChildren, root.Val)
}

You got the idea, right? 💡

In summary, what I want say to you is that the recursive binary tree definition is a great start point when thinking about resolution of some problem related to binary trees. Of course it's not a silver bullet, since some questions may require different approaches like traversing iteratively by levels instead of recursively, but this is a subject for another post.

Hope it'll be useful for you!