I'm Lynn, a software engineer and a recent graduate from the University of Chicago. This is the second course in my Coding Interview Crash Course Series. Feel free to check out my YouTube channel, Lynn's DevLab, to stay updated on this series.

This crash course is about Tree Traversal. If you just want to dive right in, you can find the course here (and linked at the bottom of this article). If you want a little more info, read on. 😎

Who is the Course for and What are Tree Traversal Algorithms? 🌳

You will get the most of this course if you already know a bit about the Tree data structure. Check out these tutorials if you need a refresher.

We will cover the traversal algorithms for both Binary Trees and N-ary Trees (in which each parent node has an arbitrary number of children).

If you have heard about Binary Search Trees (BST) before, that's a special type of Binary Tree so the techniques we are going to learn here also apply.

Trees are a favorite interview subject among top tech companies like Google, Microsoft, and Facebook, so let's crunch this topic!

We will learn about four traversal techniques and solve their corresponding LeetCode problems hands-on.

The four techniques are:

• Pre-order (Depth-First Search, DFS)

• Post-order

• In-order

• Level-order (Breadth-First Search, BFS).

Course Outline

This course video runs for a total of 30 minutes and features:

• A high-level description of the four traversal techniques: pre-order, post-order, in-order, and level-order

• Recursive implementations of pre-order, post-order, and in-order (Note: this doesn't apply to level-order)

• Iterative implementations of pre-order, post-order, in-order, and level-order

• An extension of the templates from Binary Trees to N-ary Trees

Let's dive into each of the four techniques below.

Tree Traversal Demonstration Using an Example Tree

We will use the following tree to demonstrate the output from the four traversal techniques.

Note that this tree is a simple Binary Tree, not a Binary Search Tree (BST). A BST is a special type of Binary Tree, so our techniques also apply. Also, in-order traversal becomes especially interesting when we work with a BST, as we will see below.

An example Binary Tree. Note that it's not a Binary Search Tree (BST).

Given this tree, the traversal result from the four techniques are as follows:

• Pre-order: 1, 2, 4, 5, 3

• Post-order: 4, 5, 2, 3, 1

• In-order: 4, 2, 5, 1, 3

• Level-order: 1, 2, 3, 4, 5

Pre-order Traversal

Pre-order traversal is also known as Depth-First Search (DFS) if we analyze the tree as a graph and take the tree root node as our starting node in the search.

As in the example above, we go all the way down to the leftmost node before visiting any other node that is a left child of some parent node.

Pre-order traversal allows us to explore roots before leaves, and is hence ideal for tasks like copying a tree.

Post-order Traversal

Post-order traversal does the opposite of pre-order traversal, allowing us to explore leaves before roots.

In-order Traversal

In-order traversal is especially useful for flattening a tree into an array representation.

For a Binary Search Tree like below, in-order traversal outputs an array in a sorted, non-decreasing order: -4, 3, 2, 5, 18.

Binary Search Tree example

Level-order Traversal

Level-order traversal is also known as Breadth-First Search (BFS) if we consider the tree as a graph and start our search from the tree root node.

We visit every node on the current level (depth) before moving onto those on the next level. Effectively, we visit the immediate neighbor of (one step away from) our current node before visiting neighbors that are farther away.

How to Implement these Four Techniques

We will use the following definition for a node of a Binary Tree:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

Recursive implementation

Recursive implementations are the most straightforward. The most important thing to remember is the order in which we concatenate the results from the two recursive calls (one on the left subtree and one on the right subtree) with the value of the current node.

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

Iterative implementation

Compared to recursive implementations, iterative implementations are non-trivial. Most require that we use either a stack or a queue to keep track of the nodes that we need to visit.

def preorder(self, root):
    if not root:
        return []
    ret = []
    stack = [root]
    while stack:
        node = stack.pop()
        ret.append(node.val)
        # note that we append the right child before the left child
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return ret

def postorder(self, root):
    if not root:
        return []
    from collections import deque
    ret = deque()
    stack = [root]
    while stack:
        node = stack.pop()
        ret.appendleft(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return ret

The implementation for in-order traversal looks quite different from pre-order and post-order:

def inorder(self, root):
    if not root:
        return []
    ret = []
    stack = []
    while root is not None or stack:
        while root is not None:
            stack.append(root)
            root = root.left
        root = stack.pop()
        ret.append(root.val)
        root = root.right
    return ret

Lastly, we have level-order traversal, where we will output the result as [[nodes on the first level], [nodes on the second level], [nodes on the third level], ...].

def levelorder(self, root):
    if not root:
        return []
    ret = []
    from collections import deque
    queue = deque([root])
    while queue:
        ret_row = []
        # fixed size for current level
        for _ in range(len(queue)):
            node = queue.popleft()
            ret_row.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        ret.append(ret_row)
    return ret

N-ary Trees

We now extend our templates from handling Binary Trees to handling N-ary Trees. We use the following definition for the node of an N-ary Tree:

class Node:
    def __init__(self, val=None, children=[]):
        self.val = val
        self.children = children

To extend our iterative implementations to handle N-ary Trees, all we need to do is to make sure that we are appending the child nodes that we will visit in a correct order.

Recall that in pre-order traversal, we appended the right child before the left child. So when appending the children of a node of an N-ary Tree, we need to reverse the list of children.

def preorder(self, root):
    if not root:
        return []
    ret = []
    stack = [root]
    while stack:
        node = stack.pop()
        ret.append(node.val)
        # reverse the list of children
        for child in node.children[::-1]:
            stack.append(child)
    return ret

For the other traversal techniques, since we are appending the children from the left to the right, we can iterative over the list of children normally:

def postorder(self, root):
    if not root:
        return []
    from collections import deque
    ret = deque()
    stack = [root]
    while stack:
        node = stack.pop()
        ret.appendleft(node.val)
        for child in node.children:
            stack.append(child)
    return ret

def levelorder(self, root):
    if not root:
        return []
    ret = []
    from collections import deque
    queue = deque([root])
    while queue:
        ret_row = []
        # fixed size for current level
        for _ in range(len(queue)):
            node = queue.popleft()
            ret_row.append(node.val)
            for child in node.children:
                queue.append(child)
        ret.append(ret_row)
    return ret

And now we can apply our tree traversal templates to trees that have an arbitrary number of children at each node.

Conclusion

In this crash course on tree traversal, we learned four techniques: pre-order, post-order, in-order, and level-order. We discussed how they differ and what tasks they are best for.

We also implemented them both in a recursive fashion and in an iterative one. Last but not least, we extended the techniques to deal with not only Binary Trees, but N-ary Trees.

I hope now you feel more confident about tree traversal interview questions. This is also a nice segue into the topic of my next crash course on graph traversal.

With the knowledge of pre-order traversal and level-order traversal, DFS and BFS won't be completely out of the blue for you 🤓 I will even talk about how I applied graph traversal when developing an algorithm for my match-three game, Clicky Galaxy, so stay tuned!

Resources

Watch the course here:

Access the code template on my GitHub:

Check out the whole crash course series:

And lastly, feel free to subscribe to my YouTube channel for more content like this :)

Tree-based algorithms are popular machine learning methods used to solve supervised learning problems. These algorithms are flexible and can solve any kind of problem at hand (classification or regression).

Tree-based algorithms tend to use the mean for continuous features or mode for categorical features when making predictions on training samples in the regions they belong to. They also produce predictions with high accuracy, stability, and ease of interpretation.

Examples of Tree-based Algorithms

There are different tree-based algorithms that you can use, such as

• Decision Trees
• Random Forest
• Gradient Boosting
• Bagging (Bootstrap Aggregation)

So every data scientist should learn these algorithms and use them in their machine learning projects.

In this article, you will learn more about the Random forest algorithm. After completing this article, you should be proficient at using the random forest algorithm to solve and build predictive models for classification problems with scikit-learn.

What is Random Forest?

Random forest is one of the most popular tree-based supervised learning algorithms. It is also the most flexible and easy to use.

The algorithm can be used to solve both classification and regression problems. Random forest tends to combine hundreds of decision trees and then trains each decision tree on a different sample of the observations.

The final predictions of the random forest are made by averaging the predictions of each individual tree.

The benefits of random forests are numerous. The individual decision trees tend to overfit to the training data but random forest can mitigate that issue by averaging the prediction results from different trees. This gives random forests a higher predictive accuracy than a single decision tree.

The random forest algorithm can also help you to find features that are important in your dataset. It lies at the base of the Boruta algorithm, which selects important features in a dataset.

Random forest has been used in a variety of applications, for example to provide recommendations of different products to customers in e-commerce.

In medicine, a random forest algorithm can be used to identify the patient’s disease by analyzing the patient’s medical record.

Also in the banking sector, it can be used to easily determine whether the customer is fraudulent or legitimate.

How does the Random Forest algorithm work?

The random forest algorithm works by completing the following steps:

Step 1: The algorithm select random samples from the dataset provided.

Step 2: The algorithm will create a decision tree for each sample selected. Then it will get a prediction result from each decision tree created.

Step 3: Voting will then be performed for every predicted result. For a classification problem, it will use mode, and for a regression problem, it will use mean.

Step 4: And finally, the algorithm will select the most voted prediction result as the final prediction.

how it works

Random Forest in Practice

Now that you know the ins and outs of the random forest algorithm, let's build a random forest classifier.

We will build a random forest classifier using the Pima Indians Diabetes dataset. The Pima Indians Diabetes Dataset involves predicting the onset of diabetes within 5 years based on provided medical details. This is a binary classification problem.

Our task is to analyze and create a model on the Pima Indian Diabetes dataset to predict if a particular patient is at a risk of developing diabetes, given other independent factors.

We will start by importing important packages that we will use to load the dataset and create a random forest classifier. We will use the scikit-learn library to load and use the random forest algorithm.

# import important packages
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

%matplotlib inline

from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score
from sklearn.preprocessing import StandardScaler, MinMaxScaler
import pandas_profiling

from matplotlib import rcParams
import warnings

warnings.filterwarnings("ignore")

# figure size in inches
rcParams["figure.figsize"] = 10, 6
np.random.seed(42)

Dataset

Then load the dataset from the data directory:

# Load dataset
data = pd.read_csv("../data/pima_indians_diabetes.csv")

Now we can observe the sample of the dataset.

# show sample of the dataset
data.sample(5)

As you can see, in our dataset we have different features with numerical values.

Let's understand the list of features we have in this dataset.

# show columns
data.columns

In this dataset, there are 8 input features and 1 output / target feature. Missing values are believed to be encoded with zero values. The meaning of the variable names are as follows (from the first to the last feature):

• Number of times pregnant.
• Plasma glucose concentration a 2 hours in an oral glucose tolerance test.
• Diastolic blood pressure (mm Hg).
• Triceps skinfold thickness (mm).
• 2-hour serum insulin (mu U/ml).
• Body mass index (weight in kg/(height in m)^2).
• Diabetes pedigree function.
• Age (years).
• Class variable (0 or 1).

Then we split the dataset into independent features and target feature. Our target feature for this dataset is called class.

# split data into input and taget variable(s)

X = data.drop("class", axis=1)
y = data["class"]

Preprocessing the Dataset

Before we create a model we need to standardize our independent features by using the standardScaler method from scikit-learn.

# standardize the dataset
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

You can learn more on how and why to standardize your data from this article by clicking here.

Splitting the dataset into Training and Test data

We now split our processed dataset into training and test data. The test data will be 10% of the entire processed dataset.

# split into train and test set
X_train, X_test, y_train, y_test = train_test_split(
    X_scaled, y, stratify=y, test_size=0.10, random_state=42
)

Building the Random Forest Classifier

Now is time to create our random forest classifier and then train it on the train set. We will also pass the number of trees (100) in the forest we want to use through the parameter called n_estimators.

# create the classifier
classifier = RandomForestClassifier(n_estimators=100)

# Train the model using the training sets
classifier.fit(X_train, y_train)

The above output shows different parameter values of the random forest classifier used during the training process on the train data.

After training we can perform prediction on the test data.

# predictin on the test set
y_pred = classifier.predict(X_test)

Then we check the accuracy using actual and predicted values from the test data.

# Calculate Model Accuracy
print("Accuracy:", accuracy_score(y_test, y_pred))

Accuracy: 0.8051948051948052

Our accuracy is around 80.5% which is good. But we can always make it better.

Identify Important Features

As I said before, we can also check the important features by using the featureimportances variable from the random forest algorithm in scikit-learn.

# check Important features
feature_importances_df = pd.DataFrame(
    {"feature": list(X.columns), "importance": classifier.feature_importances_}
).sort_values("importance", ascending=False)

# Display
feature_importances_df

Important Features

The figure above shows the relative importance of features and their contribution to the model. We can also visualize these features and their scores using the seaborn and matplotlib libraries.

# visualize important featuers

# Creating a bar plot
sns.barplot(x=feature_importances_df.feature, y=feature_importances_df.importance)
# Add labels to your

plt.xlabel("Feature Importance Score")
plt.ylabel("Features")
plt.title("Visualizing Important Features")
plt.xticks(
    rotation=45, horizontalalignment="right", fontweight="light", fontsize="x-large"
)
plt.show()

From the figure above, you can see the triceps_skinfold_thickness feature has low importance and does not contribute much to the prediction.

This means that we can remove this feature and train our random forest classifier again and then see if it can improve its performance on the test data.

# load data with selected features
X = data.drop(["class", "triceps_skinfold_thickness"], axis=1)
y = data["class"]

# standardize the dataset
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# split into train and test set
X_train, X_test, y_train, y_test = train_test_split(
    X_scaled, y, stratify=y, test_size=0.10, random_state=42
)

We will train the random forest algorithm with the selected processed features from our dataset, perform predictions, and then find the accuracy of the model.

# Create a Random Classifier
clf = RandomForestClassifier(n_estimators=100)

# Train the model using the training sets
clf.fit(X_train, y_train)

# prediction on test set
y_pred = clf.predict(X_test)

# Calculate Model Accuracy,
print("Accuracy:", accuracy_score(y_test, y_pred))

Accuracy: 0.8181818181818182

Now the model accuracy has increased from 80.5% to 81.8% after we removed the least important feature called _triceps_skinfoldthickness.

This suggests that it is very important to check important features and see if you can remove the least important features to increase your model's performance.

Wrapping up

Tree-based algorithms are really important for every data scientist to learn. In this article, you've learned the basics of tree-based algorithms and how to create a classification model by using the random forest algorithm.

I also recommend you try other types of tree-based algorithms such as the Extra-trees algorithm.

You can download the dataset and notebook used in this article here: https://github.com/Davisy/Random-Forest-classification-Tutorial

Congratulations, you have made it to the end of this article!

If you learned something new or enjoyed reading this article, please share it so that others can see it. Until then, see you in the next post! I can also be reached on Twitter @Davis_McDavid

What is Depth First Search?

Depth first search is a popular graph traversal algorithm. One application of depth first search in real world applications is in site mapping.

A site map is a list of pages of a web site. They are organised in a hierarchical manner and describe the whole structure of a website starting from a root node.

The Algorithm

Site mapping involves loading a root link, parsing the internal links on the page and then recursively applying the same process to those links. This gives us a graph data structure, but for simplicity, we can assume that it's a tree.

The Problem

If we implemented the algorithm that way, loading and parsing HTML pages takes time and blocks the whole traversal process.

Suppose an HTTP response takes an average of 300ms and there are 100 pages on the site to map. 300*100 = 30000ms => 30 seconds. So, the process will remain idle for 300 seconds.

How Can We Improve This?

In the time that a page loads, you can send multiple HTTP requests and parse the received HTML pages if you implement a multi-threaded architecture.

This concurrent method is 7x faster than the one previously mentioned.

Implementing threads may set off the alarm bell in many developers' mind. However, Golang provides you with a beautiful set of concepts like goroutines, channels, and synchronization utilities to make the job much easier.

I talked about site mapping earlier, however, it is much better and simpler if you learn how to program a depth first search algorithm for a binary tree. You can apply what you'll learn in this article to a lot of different things.

Let's get started!

You can find the code used in this article here on GitHub.

Setting Up the Tree

Node Definition

A node struct is the basic building block of your binary tree. It has a data, a left child and right child pointer. To simulate the delay in processing a node, you have to assign a random sleep time in microseconds.

type Node struct {
    Data interface{}
    Sleep time.Duration
    Left *Node
    Right *Node
}

Node Generator Function

NewNode() returns a pointer to the a new node. Sleep is assigned a duration of 0-100 microseconds.

func NewNode(data interface{}) *Node {

    node := new(Node)

    node.Data = data
    node.Left = nil
    node.Right = nil

    rand.Seed(time.Now().UTC().UnixNano())
    duration := int64(rand.Intn(100))
    node.Sleep = time.Duration(duration) * time.Microsecond

    return node
}

Now you've set up your tree and can implement the depth first search and a function to process the node.

Single-Threaded Depth First Search

ProcessNode()

ProcessNode() is a function that will be invoked when the node has to be processed during a traversal.

Normally you would print or store the node's value. However, to show the benefits of goroutines, you'll have to implement a compute intensive task that takes somewhere around 1 second.

During each iteration, the node sleeps for n.Sleep microseconds and prints out Node <data> ✅ once the task completes.

func (n *Node) ProcessNode() {

    var hello []int

    for i := 0; i < 10000; i++ {
        time.Sleep(n.Sleep)
        hello = append(hello, i)
    }

    fmt.Printf("Node %v ✅\n", n.Data)
}

Depth First Search Recursive Function

This is a single-threaded depth first search function implemented via recursion — it might look familiar to those who have written it before.

func (n *Node) DFS() {

    if n == nil {
        return
    }

    n.Left.DFS()
    n.ProcessNode()
    n.Right.DFS()
}

Implementing the main() Function

In the main function, create a complete binary tree that consists of 7 nodes.

To see how much time has elapsed, initiate start and then begin the DFS at the root. Once it completes, main() prints out the time that has elapsed.

var wg sync.WaitGroup

func main() {

    root := NewNode(1)
    root.Left = NewNode(2)
    root.Right = NewNode(3)
    root.Left.Left = NewNode(4)
    root.Left.Right = NewNode(5)
    root.Right.Left = NewNode(6)
    root.Right.Right = NewNode(7)

    start := time.Now()
    root.DFS()
    fmt.Printf("\nTime elapsed: %v\n\n", time.Since(start))

}

Output

It took 8.75s for the depth first search to complete.

Most of the time, the processor was idle as each node was being processed. It also prevented other nodes from processing while it completed its sleep time.

In the real world, this situation occurs during I/O or external HTTP calls.

Node 4 ✅
Node 2 ✅
Node 5 ✅
Node 1 ✅
Node 6 ✅
Node 3 ✅
Node 7 ✅

Time elapsed: 8.75086767s

Supercharge Your Depth First Search with Goroutines

Converting the process and depth first search functions involves only minor changes when compared to other programming languages:

1. Calling the recursive function with the go command.
2. Maintaining a waitGroup which keeps track of the in process function so the program doesn't exit without all of them completing.

DFSParallel()

wg.Add(1): Before going into recursion, add the goroutine that will be started to the waitGroup.

You can also run wg.Add(3) and then start the three goroutines and it will do the job. However, this is more aesthetic and clearly denotes what is going to happen.

defer wg.Done(): decreases the waitGroup counter by 1 when the function returns. This conveys that the routine has completed.

go: Starts the function in a new goroutine.

func (n *Node) DFSParallel() {

    defer wg.Done()

    if n == nil {
        return
    }

    wg.Add(1)
    go n.Left.DFSParallel()

    wg.Add(1)
    go n.ProcessNodeParallel()

    wg.Add(1)
    go n.Right.DFSParallel()
}

ProcessNodeParallel()

Nothing much to be done here, just add a defer wg.Done() after the function starts. It'll inform waitGroup that this goroutine has finished.

func (n *Node) ProcessNodeParallel() {

    defer wg.Done()

    var hello []int

    for i := 0; i < 10000; i++ {
        time.Sleep(n.Sleep)
        hello = append(hello, i)
    }

    fmt.Printf("Node %v ✅\n", n.Data)
}

###

Calling DFSParallel() in main()

GOMAXPROCS tells the Go compiler to run threads on all logical cores available on the computer.

This will help you to process multiple nodes as well. The concurrent design pattern that has been implemented here shows the benefit of having multiple cores on the computer. Not only can the program process other nodes while one is sleeping, but it can also process multiple nodes at the same time.

You can start the DFSParallel() as a goroutine as before and add it to the wait group.

wg.Wait() waits for all goroutines to be completed. It waits for the goroutines count to be 0 and then moves the control forward.

...
    // Go will use maximum number of processors available to process goroutines
    processors := runtime.GOMAXPROCS(runtime.NumCPU())

    fmt.Printf("\nTime elapsed: %v\n\n", time.Since(start))

    // Starts the timer
    start = time.Now()

    // Adds one goroutine the WaitGroup
    wg.Add(1)
    // Start the DFS Goroutine
    go root.DFSParallel()
    // Waits for all goroutines to complete
    wg.Wait()

    fmt.Printf("\nProcessors: %v Time elapsed: %v\n", processors, time.Since(start))


}

Output

Node 7 ✅
Node 4 ✅
Node 2 ✅
Node 6 ✅
Node 5 ✅
Node 1 ✅
Node 3 ✅

Processors: 8 Time elapsed: 1.295332809s

As expected, the depth first search algorithm completes in just 1.3 seconds as opposed to the 8.7 seconds in the previous implementation.

Explanation

Normal Implementation

The functions were running serially in a pre-ordered manner as you would expect. Each function was taking ~1.1 seconds to complete leading to the long run time.

However, each node sleeps for ~1 second as well, during which the processors remain idle as everything is running in one thread.

Normal Implementation Time Graph (x-axis in Seconds)

Concurrent Implementation

The functions were running independently and almost every one of them started at roughly ~ 0th second. They ran for 1 second and every thread completed.

However you can see that the order is not the same as the previous implementation. This is because they are running independently and finish at different times. Since they all started at roughly the same time, the traversal completed in roughly the duration of a single function's runtime.

Concurrent Implementation (x-axis in seconds)

Conclusion

I found this result to be pretty amazing since it didn't take me more than a few concepts and 5-6 extra lines to make this program 7x faster.

This technique can prove to be a major boost to your Go program if you can identify functions which can run independently at the same time. If your functions require synchronization, you can use channels to achieve that task.

You can find the code used in this article here on GitHub.

Supplementary Stuff

1. https://medium.com/rungo/anatomy-of-goroutines-in-go-concurrency-in-go-a4cb9272ff88
2. https://blog.golang.org/defer-panic-and-recover
3. https://medium.com/@houzier.saurav/dfs-and-bfs-golang-d5818ec690d3
4. https://medium.com/rungo/anatomy-of-channels-in-go-concurrency-in-go-1ec336086adb

The tree data structure can form some of the most useful and complex data structures in all of programming. In fact the tree is so powerful that I can make the bold claim:

Once you understand trees you'll be able to understand many other data structures and algorithms with ease.

There is one caveat. There are so many types of trees it may be impossible to know where to start! There are B-trees, Red Black Trees, Binary Trees, AVL Trees and many others. There are abundant choices and each seems valuable to learn.

This presents a problem. As someone learning about trees you may find yourself asking, which tree data structure do I learn about first? Which tree is most important for me? There are so many, where do I start?

Learning about trees is like learning about the numerous marvels in our current world. We have a lot of choices, in fact we may even have too much choice.

Psychologists call it Overchoice or "choice overload", that is when faced with many options, people have a difficult choice deciding on what to do. I call it a beginning coder's worst nightmare.

However there is no need to panic. From my knowledge of using the tree data structure, as with most things in life, the Pareto principle (what we call the 80/20 rule) applies.

What this means is that as a programmer, 80% of cases where you will need to use trees will be covered by approximately 20% of the types of trees that you will attempt to learn.

For this reason we will focus only on these 20% which I think are the most important trees you need to understand. Don't get me wrong here, I'm not saying don't learn other types of trees. I'm saying learn these first, then focus on the others to really get that edge.

Even when you do figure out which tree data structure you want to learn, you are faced with another problem.

There are a lot of resources out there that teach you about trees, however they all present you with some code in a particular language be it JavaScript, Java, Python or others as part of the explanation.

In this post I break that status quo and teach you about the essential tree data structures, and all without having you write a single line of code.

Join me on a journey into the world of trees, regardless of which programming language you are using, you will be able to learn all the basics you need to know about the tree data structure.

Getting to the Root of Trees

Let's get to the root of our discussion (pun intended). The way I like to explain trees is by relating it to something we are all familiar with, that of the biological tree. In case you are not familiar, let's look at one right now:

A Biological Tree

Look at our tree, isn't it beautiful!? We see that a tree is a giant plant with a trunk, a branch and leaves. There are also roots hidden beneath the ground that also form part of the organism.

A tree in computer science isn't so different. Let's look at one here:

A Computer Science Tree

A computer science tree is very similar to a regular tree – it resembles an upside down biological tree a little doesn't it? It not only looks similar, but it also has parts that are named similar to our good ol' tangible tree.

Before we learn about the types of trees though, there are a few facts about trees you must know.

Here are 5 facts you need to know about trees:

1. Each of the circles in the tree is called a node and each line is called an edge.

2. The root node is the part of the tree that all the other parts are built upon.

3. There are parent nodes connected to other nodes in the direction of the root, and child nodes connected in the direction away from the root.

4. The last nodes of the trees are called leaves

5. The process of navigating a tree is called traversal.

If you like to see things visually, here is a diagram of the tree we looked at earlier identifying the parts:

Our Labelled Tree

You should also know that when a tree is the child of a node, it is called a subtree. Look at the diagram above, the node labelled "Parent" along with its two child nodes can be classified as a subtree.

Great, now you have an idea about basic trees. So let's dive into some of the most useful type of trees you will encounter.

The General Tree

The first type of tree we need to know about is the general tree. The general tree is what we call a superset. This is because all other types of trees are derived from the general tree.

Trees are hierarchical in the way they store data. Whereas simpler data structures may store data in a linear manner (think an array), trees are non-linear.

The general tree is the embodiment of a hierarchical tree structure as it has no restrictions on how many children each node can have, and has no restraint imposed on the hierarchy of the tree.

Example of A General Tree

The Binary Tree

It is impossible to talk about trees without talking about the binary tree (okay not totally impossible, but you know what I mean).

Simply put, a binary tree is a type of tree that has a restriction. In the binary tree, each parent can only be linked to two child nodes within the tree.

There is one binary tree type that illustrates this best: the binary search tree. Trees you see aren't just empty circles connected by lines. Each of the node in the tree has a value associated with it and the entirety of the tree is a key-value structure.

Binary search trees keep their keys sorted. They sort it like this: all the nodes are greater that the nodes in their left subtree, but are smaller than the nodes in their right subtree. Confused? Maybe a picture will help:

A Binary Search Tree

Look closely at this tree and you will learn a little secret. In the binary tree the smallest node is located at the leftmost subtree stemming from the root node. Wanna guess where we can find the largest node?

Red-Black Tree

Let's look at a variant of the binary search tree that people tend to over-complicate. I'm talking about the Red-Black Tree.

There are many cases of trees where data may be inserted and deleted. So variations of the binary search tree have been created which makes this constant insertion and deletion more efficient.

The Red-Black tree is one such configuration of the binary search tree that makes the insertion and deletion process more efficient.

The tree does this by having a bit that adds an attribute to the node. This attribute that is added on the node is color, and this color can be interpreted as red or black. Hence the name Red-Black tree.

Let's look at how a Red-Black tree many be arranged:

A Red-Black Tree

In the Red-Black tree, the root node is usually black and each red node has children that are black.

If you made it this far, then congratulations! You already understand enough to make a foray into the world of tree data structures.

Where Are Trees Used?

At this point you may be wondering what trees are used for. That's a good question! Trees are used in many facets of development including use in:

1. Databases
2. Compilers
3. Networking
4. Heaps
5. Machine Learning Algorithms

There are countless uses for trees and the only limit in their use is the imagination of the designer.

Wrapping Up

In this post we began our journey into the world of the tree. Even though we covered some ground, we merely scrapped the surface of this vast and intricate data structure.

We whet our appetite for tree data structures by covering what trees are and looked at their structure. We then discussed three common types of trees including general trees, binary trees and red-black trees. Finally we looked at some places where trees may be used.

By the end of this post you should have a solid foundation to venture into the world of trees!

Where to Go Next?

Want to learn about trees and other data structures without writing a single line of code? The pick up the book "Codeless Data Structures and Algorithms", where you'll learn all you need to know about data structures and algorithms without writing a single line of code!

We will not only greatly expand on what we learned, but we'll cover juicy topics not covered here like tree balancing, AVL trees, B-Trees, Heaps and a ton of topics in the realm of data structures and algorithms!

You can read the book here:

A BST is a data structure composed of nodes. It has the following guarantees:

1. Each tree has a root node (at the top).
2. The root node has zero or more child nodes.
3. Each child node has zero or more child nodes, and so on.
4. Each node has up to two children.
5. For each node, its left descendants are less than the current node, which is less than the right descendants.

AVL trees have an additional guarantee:

1. The difference between the depth of right and left subtrees cannot be more than one.

In order to maintain this guarantee, implementations of AVL trees include an algorithm to rebalance the tree when adding an additional element would cause the difference in depth between the right and left trees to be greater than one.

AVL trees have a worst case lookup, insert and delete time of O(log n).

Right Rotation

_Source: https://github.com/HebleV/valet_parking/tree/master/images_

Left Rotation

_Source: https://github.com/HebleV/valet_parking/tree/master/images_

AVL Insertion Process

This works similarly to a normal binary search tree insertion. After the insertion, you fix the AVL property by using left or right rotations.

• If there is an imbalance in left child of right subtree, then you perform a left-right rotation.
• If there is an imbalance in left child of left subtree, then you perform a right rotation.
• If there is an imbalance in right child of right subtree, then you perform a left rotation.
• If there is an imbalance in right child of left subtree, then you perform a right-left rotation.

Example

Here's an example of an AVL tree in Python:

class node:
    def __init__(self,value=None):
        self.value=value
        self.left_child=None
        self.right_child=None
        self.parent=None # pointer to parent node in tree
        self.height=1 # height of node in tree (max dist. to leaf) NEW FOR AVL

class AVLTree:
    def __init__(self):
        self.root=None

    def __repr__(self):
        if self.root==None: return ''
        content='\n' # to hold final string
        cur_nodes=[self.root] # all nodes at current level
        cur_height=self.root.height # height of nodes at current level
        sep=' '*(2**(cur_height-1)) # variable sized separator between elements
        while True:
            cur_height+=-1 # decrement current height
            if len(cur_nodes)==0: break
            cur_row=' '
            next_row=''
            next_nodes=[]

            if all(n is None for n in cur_nodes):
                break

            for n in cur_nodes:

                if n==None:
                    cur_row+='   '+sep
                    next_row+='   '+sep
                    next_nodes.extend([None,None])
                    continue

                if n.value!=None:       
                    buf=' '*int((5-len(str(n.value)))/2)
                    cur_row+='%s%s%s'%(buf,str(n.value),buf)+sep
                else:
                    cur_row+=' '*5+sep

                if n.left_child!=None:  
                    next_nodes.append(n.left_child)
                    next_row+=' /'+sep
                else:
                    next_row+='  '+sep
                    next_nodes.append(None)

                if n.right_child!=None: 
                    next_nodes.append(n.right_child)
                    next_row+='\ '+sep
                else:
                    next_row+='  '+sep
                    next_nodes.append(None)

            content+=(cur_height*'   '+cur_row+'\n'+cur_height*'   '+next_row+'\n')
            cur_nodes=next_nodes
            sep=' '*int(len(sep)/2) # cut separator size in half
        return content

    def insert(self,value):
        if self.root==None:
            self.root=node(value)
        else:
            self._insert(value,self.root)

    def _insert(self,value,cur_node):
        if value<cur_node.value:
            if cur_node.left_child==None:
                cur_node.left_child=node(value)
                cur_node.left_child.parent=cur_node # set parent
                self._inspect_insertion(cur_node.left_child)
            else:
                self._insert(value,cur_node.left_child)
        elif value>cur_node.value:
            if cur_node.right_child==None:
                cur_node.right_child=node(value)
                cur_node.right_child.parent=cur_node # set parent
                self._inspect_insertion(cur_node.right_child)
            else:
                self._insert(value,cur_node.right_child)
        else:
            print("Value already in tree!")

    def print_tree(self):
        if self.root!=None:
            self._print_tree(self.root)

    def _print_tree(self,cur_node):
        if cur_node!=None:
            self._print_tree(cur_node.left_child)
            print ('%s, h=%d'%(str(cur_node.value),cur_node.height))
            self._print_tree(cur_node.right_child)

    def height(self):
        if self.root!=None:
            return self._height(self.root,0)
        else:
            return 0

    def _height(self,cur_node,cur_height):
        if cur_node==None: return cur_height
        left_height=self._height(cur_node.left_child,cur_height+1)
        right_height=self._height(cur_node.right_child,cur_height+1)
        return max(left_height,right_height)

    def find(self,value):
        if self.root!=None:
            return self._find(value,self.root)
        else:
            return None

    def _find(self,value,cur_node):
        if value==cur_node.value:
            return cur_node
        elif value<cur_node.value and cur_node.left_child!=None:
            return self._find(value,cur_node.left_child)
        elif value>cur_node.value and cur_node.right_child!=None:
            return self._find(value,cur_node.right_child)

    def delete_value(self,value):
        return self.delete_node(self.find(value))

    def delete_node(self,node):

        ## -----
        # Improvements since prior lesson

        # Protect against deleting a node not found in the tree
        if node==None or self.find(node.value)==None:
            print("Node to be deleted not found in the tree!")
            return None 
        ## -----

        # returns the node with min value in tree rooted at input node
        def min_value_node(n):
            current=n
            while current.left_child!=None:
                current=current.left_child
            return current

        # returns the number of children for the specified node
        def num_children(n):
            num_children=0
            if n.left_child!=None: num_children+=1
            if n.right_child!=None: num_children+=1
            return num_children

        # get the parent of the node to be deleted
        node_parent=node.parent

        # get the number of children of the node to be deleted
        node_children=num_children(node)

        # break operation into different cases based on the
        # structure of the tree & node to be deleted

        # CASE 1 (node has no children)
        if node_children==0:

            if node_parent!=None:
                # remove reference to the node from the parent
                if node_parent.left_child==node:
                    node_parent.left_child=None
                else:
                    node_parent.right_child=None
            else:
                self.root=None

        # CASE 2 (node has a single child)
        if node_children==1:

            # get the single child node
            if node.left_child!=None:
                child=node.left_child
            else:
                child=node.right_child

            if node_parent!=None:
                # replace the node to be deleted with its child
                if node_parent.left_child==node:
                    node_parent.left_child=child
                else:
                    node_parent.right_child=child
            else:
                self.root=child

            # correct the parent pointer in node
            child.parent=node_parent

        # CASE 3 (node has two children)
        if node_children==2:

            # get the inorder successor of the deleted node
            successor=min_value_node(node.right_child)

            # copy the inorder successor's value to the node formerly
            # holding the value we wished to delete
            node.value=successor.value

            # delete the inorder successor now that it's value was
            # copied into the other node
            self.delete_node(successor)

            # exit function so we don't call the _inspect_deletion twice
            return

        if node_parent!=None:
            # fix the height of the parent of current node
            node_parent.height=1+max(self.get_height(node_parent.left_child),self.get_height(node_parent.right_child))

            # begin to traverse back up the tree checking if there are
            # any sections which now invalidate the AVL balance rules
            self._inspect_deletion(node_parent)

    def search(self,value):
        if self.root!=None:
            return self._search(value,self.root)
        else:
            return False

    def _search(self,value,cur_node):
        if value==cur_node.value:
            return True
        elif value<cur_node.value and cur_node.left_child!=None:
            return self._search(value,cur_node.left_child)
        elif value>cur_node.value and cur_node.right_child!=None:
            return self._search(value,cur_node.right_child)
        return False 


    # Functions added for AVL...

    def _inspect_insertion(self,cur_node,path=[]):
        if cur_node.parent==None: return
        path=[cur_node]+path

        left_height =self.get_height(cur_node.parent.left_child)
        right_height=self.get_height(cur_node.parent.right_child)

        if abs(left_height-right_height)>1:
            path=[cur_node.parent]+path
            self._rebalance_node(path[0],path[1],path[2])
            return

        new_height=1+cur_node.height 
        if new_height>cur_node.parent.height:
            cur_node.parent.height=new_height

        self._inspect_insertion(cur_node.parent,path)

    def _inspect_deletion(self,cur_node):
        if cur_node==None: return

        left_height =self.get_height(cur_node.left_child)
        right_height=self.get_height(cur_node.right_child)

        if abs(left_height-right_height)>1:
            y=self.taller_child(cur_node)
            x=self.taller_child(y)
            self._rebalance_node(cur_node,y,x)

        self._inspect_deletion(cur_node.parent)

    def _rebalance_node(self,z,y,x):
        if y==z.left_child and x==y.left_child:
            self._right_rotate(z)
        elif y==z.left_child and x==y.right_child:
            self._left_rotate(y)
            self._right_rotate(z)
        elif y==z.right_child and x==y.right_child:
            self._left_rotate(z)
        elif y==z.right_child and x==y.left_child:
            self._right_rotate(y)
            self._left_rotate(z)
        else:
            raise Exception('_rebalance_node: z,y,x node configuration not recognized!')

    def _right_rotate(self,z):
        sub_root=z.parent 
        y=z.left_child
        t3=y.right_child
        y.right_child=z
        z.parent=y
        z.left_child=t3
        if t3!=None: t3.parent=z
        y.parent=sub_root
        if y.parent==None:
                self.root=y
        else:
            if y.parent.left_child==z:
                y.parent.left_child=y
            else:
                y.parent.right_child=y        
        z.height=1+max(self.get_height(z.left_child),
            self.get_height(z.right_child))
        y.height=1+max(self.get_height(y.left_child),
            self.get_height(y.right_child))

    def _left_rotate(self,z):
        sub_root=z.parent 
        y=z.right_child
        t2=y.left_child
        y.left_child=z
        z.parent=y
        z.right_child=t2
        if t2!=None: t2.parent=z
        y.parent=sub_root
        if y.parent==None: 
            self.root=y
        else:
            if y.parent.left_child==z:
                y.parent.left_child=y
            else:
                y.parent.right_child=y
        z.height=1+max(self.get_height(z.left_child),
            self.get_height(z.right_child))
        y.height=1+max(self.get_height(y.left_child),
            self.get_height(y.right_child))

    def get_height(self,cur_node):
        if cur_node==None: return 0
        return cur_node.height

    def taller_child(self,cur_node):
        left=self.get_height(cur_node.left_child)
        right=self.get_height(cur_node.right_child)
        return cur_node.left_child if left>=right else cur_node.right_child

More info on binary search:

• Binary search basics
• Binary search trees explained with examples
• Binary data structures: intro to trees (and heaps)

B-Tree is a self-balancing search tree.

In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory.

To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time.

The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations (search, insert, delete, max, min, etc) require O(h) disk accesses where h is height of the tree. B-tree is a fat tree.

Height of B-Trees is kept low by putting maximum possible keys in a B-Tree node. Generally, a B-Tree node size is kept equal to the disk block size. Since h is low for B-Tree, total disk accesses for most of the operations are reduced significantly compared to balanced Binary Search Trees like AVL Tree, Red Black Tree, etc.

Properties of B-Tree:

1. All leaf nodes are at same level.
2. A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.
3. Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
4. All nodes (including root) may contain at most 2t – 1 keys.
5. Number of children of a node is equal to the number of keys in it plus 1.
6. All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in range from k1 and k2.
7. B-Tree grows and shrinks from root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.
8. Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(Log(n)).

Search:

Search is similar to search in Binary Search Tree. Let the key to be searched be k. We start from root and recursively traverse down. For every visited non-leaf node, if the node has key, we simply return the node. Otherwise we recur down to the appropriate child (The child which is just before the first greater key) of the node. If we reach a leaf node and don’t find k in the leaf node, we return NULL.

Traverse:

Traversal is also similar to Inorder traversal of Binary Tree. We start from the leftmost child, recursively print the leftmost child, then repeat the same process for remaining children and keys. In the end, recursively print the rightmost child.

Insert

First we search and find out to which node the key should belong to and we insert it into it. Afterwards we look for and fix these problems: If the number of keys is too high(greater than t - 1) then we move the middle key to the nodes parent. We do this recursively up until root. If the number of keys in the root is too high, then we make the middle key to be the new root of the whole tree and connect it to the node it was in before.

Time Analysis for B-Tree:

Suppose a B-tree has n elements and M is the maximum number of children a node can have. What is the maximum depth the tree could have? What is the minimum depth the tree could have?

• The worst-case depth (maximum depth) of a B-tree is: logM/2 n.
• The best-case depth (minimum depth) of a B-tree is: logM n.

A tree is a data structure composed of nodes that has the following characteristics:

1. Each tree has a root node at the top (also known as Parent Node) containing some value (can be any datatype).
2. The root node has zero or more child nodes.
3. Each child node has zero or more child nodes, and so on. This creates a subtree in the tree. Every node has its own subtree made up of its children and their children, etc. This means that every node on its own can be a tree.

A binary search tree (BST) adds these two characteristics:

1. Each node has a maximum of up to two children.
2. For each node, the values of its left descendent nodes are less than that of the current node, which in turn is less than the right descendent nodes (if any).

The BST is built on the idea of the binary search algorithm, which allows for fast lookup, insertion and removal of nodes. The way that they are set up means that, on average, each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree, O(log n) . However, some times the worst case can happen, when the tree isn't balanced and the time complexity is O(n) for all three of these functions. That is why self-balancing trees (AVL, red-black, etc.) are a lot more effective than the basic BST.

Worst case scenario example: This can happen when you keep adding nodes that are always larger than the node before (its parent), the same can happen when you always add nodes with values lower than their parents.

Basic operations on a BST

• Create: creates an empty tree.
• Insert: insert a node in the tree.
• Search: Searches for a node in the tree.
• Delete: deletes a node from the tree.
• Inorder: in-order traversal of the tree.
• Preorder: pre-order traversal of the tree.
• Postorder: post-order traversal of the tree.

Create

Initially an empty tree without any nodes is created. The variable/identifier which must point to the root node is initialized with a NULL value.

Search

You always start searching the tree at the root node and go down from there. You compare the data in each node with the one you are looking for. If the compared node doesn't match then you either proceed to the right child or the left child, which depends on the outcome of the following comparison: If the node that you are searching for is lower than the one you were comparing it with, you proceed to the left child, otherwise (if it's larger) you go to the right child. Why? Because the BST is structured (as per its definition), that the right child is always larger than the parent and the left child is always lesser.

Breadth-first search (BFS)

Breadth first search is an algorithm used to traverse a BST. It begins at the root node and travels in a lateral manner (side to side), searching for the desired node. This type of search can be described as O(n) given that each node is visited once and the size of the tree directly correlates to the length of the search.

Depth-first search (DFS)

With a Depth-first search approach, we start with the root node and travel down a single branch. If the desired node is found along that branch, great, but if not, continue upwards and search unvisited nodes. This type of search also has a big O notation of O(n).

Insert

It is very similar to the search function. You again start at the root of the tree and go down recursively, searching for the right place to insert our new node, in the same way as explained in the search function. If a node with the same value is already in the tree, you can choose to either insert the duplicate or not. Some trees allow duplicates, some don't. It depends on the certain implementation.

Deletion

There are 3 cases that can happen when you are trying to delete a node. If it has,

1. No subtree (no children): This one is the easiest one. You can simply just delete the node, without any additional actions required.
2. One subtree (one child): You have to make sure that after the node is deleted, its child is then connected to the deleted node's parent.
3. Two subtrees (two children): You have to find and replace the node you want to delete with its inorder successor (the leftmost node in the right subtree).

The time complexity for creating a tree is O(1) . The time complexity for searching, inserting or deleting a node depends on the height of the tree h , so the worst case is O(h) in case of skewed trees.

Predecessor of a node

Predecessors can be described as the node that would come right before the node you are currently at. To find the predecessor of the current node, look at the right-most/largest leaf node in the left subtree.

Successor of a node

Successors can be described as the node that would come right after the the current node. To find the successor of the current node, look at the left-most/smallest leaf node in the right subtree.

Special types of BT

• Heap
• Red-black tree
• B-tree
• Splay tree
• N-ary tree
• Trie (Radix tree)

Runtime

Data structure: BST

• Worst-case performance: O(n)
• Best-case performance: O(1)
• Average performance: O(log n)
• Worst-case space complexity: O(1)

Where n is the number of nodes in the BST. Worst case is O(n) since BST can be unbalanced.

Implementation of BST

Here's a definition for a BST node having some data, referencing to its left and right child nodes.

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

Search Operation

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data){

      if(current != NULL) {
         printf("%d ",current->data);

         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else {                
            current = current->rightChild;
         }

         //not found
         if(current == NULL){
            return NULL;
         }
      }            
   }
   return current;
}

Insert Operation

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left

            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;

            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Delete Operation

void deleteNode(struct node* root, int data){

    if (root == NULL) root=tempnode; 

    if (data < root->key) 
        root->left = deleteNode(root->left, key); 


    else if (key > root->key) 
        root->right = deleteNode(root->right, key); 

    else
    { 
        if (root->left == NULL) 
        { 
            struct node *temp = root->right; 
            free(root); 
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            struct node *temp = root->left; 
            free(root); 
            return temp; 
        } 

        struct node* temp = minValueNode(root->right); 

        root->key = temp->key; 

        root->right = deleteNode(root->right, temp->key); 
    } 
    return root; 

}

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

• To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
• To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let's look at a couple of procedures operating on trees.

Since trees are recursively defined, it's very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

• For instance, if we have a nil tree, then its height is a 0.
• Otherwise, We're 1 plus the maximum of the left child tree and the right child tree.
• So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

if tree = nil:
    return 0
return 1 + Max(Height(tree.left),Height(tree.right))

Here is the code in C++

int maxDepth(struct node* node)
{
    if (node==NULL)
        return 0;
   else
   {
       int rDepth = maxDepth(node->right);
       int lDepth = maxDepth(node->left);

       if (lDepth > rDepth)
       {
           return(lDepth+1);
       }
       else
       {
            return(rDepth+1);
       }
   }
}

We could also look at calculating the size of a tree that is the number of nodes.

• Again, if we have a nil tree, we have zero nodes.
• Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

if tree = nil
    return 0
return 1 + Size(tree.left) + Size(tree.right)

Here is the code in C++

int treeSize(struct node* node)
{
    if (node==NULL)
        return 0;
    else
        return 1+(treeSize(node->left) + treeSize(node->right));
}

Traversal

There are 3 kinds of traversals that are done typically over a binary search tree. All these traversals have a somewhat common way of going over the nodes of the tree.

In-order

This traversal first goes over the left subtree of the root node, then accesses the current node, followed by the right subtree of the current node. The code represents the base case too, which says that an empty tree is also a binary search tree.

void inOrder(struct node* root) {
        // Base case
        if (root == null) {
                return;
        }
        // Travel the left sub-tree first.
        inOrder(root.left);
        // Print the current node value
        printf("%d ", root.data);
        // Travel the right sub-tree next.
        inOrder(root.right);
}

Pre-order

This traversal first accesses the current node value, then traverses the left and right sub-trees respectively.

void preOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Print the current node value
        printf("%d ", root.data);
        // Travel the left sub-tree first.
        preOrder(root.left);
        // Travel the right sub-tree next.
        preOrder(root.right);
}

Post-order

This traversal puts the root value at last, and goes over the left and right sub-trees first. The relative order of the left and right sub-trees remain the same. Only the position of the root changes in all the above mentioned traversals.

void postOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Travel the left sub-tree first.
        postOrder(root.left);
        // Travel the right sub-tree next.
        postOrder(root.right);
        // Print the current node value
        printf("%d ", root.data);
}

Relevant videos on freeCodeCamp YouTube channel

And Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

          18
         /   \
       /       \  
     15         30  
    /  \       /  \
  40    50   100   40

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

           18
         /    \
       /        \  
     15         30  
    /  \       /  \
  40    50   100   40
 /  \   /
8    7 9

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

          18
         /  \
       /      \  
     15        30  
    /  \      /  \
  40    50  100   40

Augmenting a BST

Sometimes we need to store some additional information with the traditional data structures to make our tasks easier. For example, consider a scenario where you are supposed to find the ith smallest number in a set. You can use brute force here but we can reduce the complexity of the problem to O(lg n) by augmenting a red-black or any self-balancing tree (where n is the number of elements in the set). We can also compute rank of any element in O(lg n) time. Let us consider a case where we are augmenting a red-black tree to store the additional information needed. Besides the usual attributes, we can store number of internal nodes in the subtree rooted at x(size of the subtree rooted at x including the node itself). Let x be any arbitrary node of a tree.

x.size = x.left.size + x.right.size + 1

While augmenting the tree, we should keep in mind, that we should be able to maintain the augmented information as well as do other operations like insertion, deletion, updating in O(lg n) time.

Since, we know that the value of x.left.size will give us the number of nodes which proceed x in the order traversal of the tree. Thus, x.left.size + 1 is the rank of x within the subtree rooted at x.

Imagine that you are enrolled in a math class at one of the most prestigious universities of the world.

You have an exam coming up real soon. Obviously, you want to perform well on the exam.

The thing about this university is that it has a clumsy set of professors. So cheating is really simple. You can easily copy from the guy sitting behind and ahead without getting caught.

The professors, in order to take control of this problem, came up with two solutions:

• The number of students sitting in a class is never fixed. And the people sitting in one class taking the test change from one test to another.
• The seating arrangement is released five minutes before the exam. The seating arrangement is alphabetical. But since the students are never fixed and new ones may get added or old ones removed from a class randomly, the arrangement has to be explicitly released for the students to know where exactly they have to sit.

Say you’re one of those lazy students who wants to cheat, despite the consequences. Five minutes before the exam when the seating arrangement is released, how do you find out who is sitting in front of you and who’s behind as quickly as possible?

You won’t be able to cheat if you don’t talk to these two people beforehand and strategize, right?

The Seating Arrangement

So the professors released the seating arrangement for the first test ever conducted this way. Say it had N students. If these students were to remain the same from one test to another, then it would have been very easy to cheat, right? Because the seating arrangement is always done alphabetically.

Therefore, the professors keep on adding or removing students from this list from one test to another, and only released these modifications before each test. This way, students could never know deterministically before a test who would be sitting in front of or behind them.

Let’s consider this problem in algorithmic terms. We are given a list of N elements where elements in this case are student’s names. This list keeps on varying from one exam to another, such that new elements can be added to the list or existing elements can be removed from the list.

Given the list of modifications at any given time T and a name N, we need to determine the elements B and A, such that B would come right before N and A would come right after N if the list were to be sorted.

Now let’s look at what data structures are available to us and what would suit this problem the best.

Oh Array, my old friend, will you help me?

Using an array seems to be a rather straightforward approach.

• We can simply put all the names on the released list in an array.
• Then we sort all the names (the list of names released might be randomly arranged) lexicographically
• And then we can find our name in the list by using a binary search procedure. This would give us the predecessor and the successor.

This seems to be a viable approach to solve this problem. The issue at hand, however, is that the students are never fixed from one exam to another. And so the list that was released for the very first exam would vary dynamically when new students were added and old ones were removed.

We can sort the list for the very first time, and then keep on adding new elements and removing old ones accordingly moving forward.

However, the complexity of adding or removing an element from an array is of the order O(n) . Since the number of students could be very large, and we don’t know how many modifications there would be before some new test, this would take a lot of time and the test would start before we could solve the problem. Remember that the modifications are released just five minutes before the test.

So what other data structure do we have where insertion and deletion can be done very quickly?

Hmmmm, maybe Linked List is my true friend after all

As far as a linked list is concerned, it has it’s own set of problems when dealing with this type of situation. Initially, we need to sort the list of elements lexicographically. Since this is a one-time operation, because it is only to be done for the first exam, the time taken here does not really matter.

From the next exam onwards, only the modifications are released. Adding or deleting an element from a linked list is a constant time operation, provided we know the location of that element in the list.

Finding an element in a linked list is a linear time operation — it takes O(n) . I know there are concepts like skip lists, but why dive into something like this when we can solve this problem in a much better fashion by using another type of data structure?

Enter Binary Search Trees, the new kid in town

Let’s look at how we can model our data using a binary search tree (BST). Then we’ll see how a BST can help us solve the problem we initially set out to solve.

A Binary Search Tree is basically a binary tree with a special way of ordering the nodes.

For a node with key k, every key in the left subtree is less than k and every key in the right subtree is greater than k.

In our case, the keys will be the names of the students.

Consider the following example to see how a binary search tree is constructed. This should lend greater clarity to the data structure.

_[http://btechsmartclass.com/DS/images/BST%20Construction.png](http://btechsmartclass.com/DS/images/BST%20Construction.png" rel="noopener" target="blank" title=")

Constructing a Binary Search Tree is not enough. We need to make sure it is balanced. The reason we say that a Binary Search Tree needs to be balanced is that, if it is not balanced, then we can have something like this:

A left skewed binary search tree.

This is known as a skewed binary search tree. If such a thing happens, then the BST basically transforms into a linked list and that is of no use to us. Therefore, we have this notion of keeping a BST balanced so that we don’t run into this problem.

The notion of balanced is defined differently by different approaches, like Red Black Trees or AVL trees. Further explanation of these trees is out of the scope of this article.

Coming back to arranging our data in a balanced BST: the keys to our BST would be the names of the students, and lexicographic matching would be used to determine the structure of the BST.

Suppose that there were a million students taking the test. If our binary search tree is balanced, then the complexity of performing any operation is upper bounded by O(log(n)) . Hence, for 1 million nodes, the maximum number of nodes to be scanned would be just 14.

That’s a lot of complexity reduction simply by arranging the data in a certain manner. That is the advantage of representing data in a balanced Binary Search Tree.

The main problem with the array-based approach was that we could not efficiently insert or delete an element from the array. And the problem with the linked list approach was that there was no efficient way for us to find an element in the linked list even if it were sorted.

As for a balanced binary search tree, the time complexity to insert, delete, or search for an element is all bounded by O(log(n)) . And this is precisely what makes this data structure extremely exciting.

However, we still haven’t solved our original problem. Given the name of a student, we want to find out the student sitting right behind and right in front of them. This boils down to finding the in-order successor and predecessor in the given Binary Search Tree.

In-order Traversal and Sorted Order in a BST

An interesting property of the binary search trees is that we can retrieve the elements in the sorted order (even reverse) by doing an in-order traversal over the binary search tree.

So the in-order successor of a node X is the element that comes right after X in the in-order traversal over the given BST. For our cheating problem, this in-order successor would be the student sitting in front of us.

The in-order predecessor of a node X is the element that comes right before X in the in-order traversal (or the element that comes right after X in the reverse in-order traversal) over the given BST. For our cheating problem, this in-order predecessor would be the student sitting right behind us.

In-order Successor in a BST

There are two different cases that we need to handle when finding the in-order successor of a node in a BST.

The first case is when the right child exists for the node whose in-order successor we are trying to find. Consider the following example.

Here we wanted to find the in-order successor of the highlighted node 8. Since it has a right child, the in-order successor would be the leftmost node in the tree with a right child, or 15 as the root. So that node would be 10 in this case.

The second case is when there is no right child.

In this case, the in-order successor has two possibilities:

1. One is where the node under consideration is the left child of its parent. In this case, the in-order successor would be the parent itself. So for our given case, the in-order successor would be 10.
2. The second case is when the current node is the right child of it’s parent. And it doesn’t have a right child. So it is the rightmost node in the BST and it has no in-order successor.

Handling the first case is fairly simple for a binary search tree. For the second case, where the given node does not have a right child (or any parent pointers), we will have to rely on our good ol’ recursion mechanism and do an in-order traversal until we figure out the parent of our given node.

So, the worst case complexity can be O(n) if the case above occurs.

Using this algorithm, we can quickly find out the student who will be sitting right in front of us in the exam.

In-order Predecessor in a BST

This is the exact reverse of the previous case.

Again, we need to handle two different cases when finding the in-order predecessor of a node in a BST. Look at the following diagrams and try to relate the two cases being referred to here.

This is the case where the node has a left child. We need to find the rightmost child of the tree rooted at this left child — the rightmost node in the tree rooted at 2.

No left child. So we need to find the parent.

If you look closely, I’ve just reversed the order of traversal here and the rest of the code is the same as before. (NOTE: this code is used when there is no left child of the node for which we want to find the in-order predecessor).

In-order predecessor becomes the reverse in-order successor.

Well now that you know how you should arrange the class seating arrangement list, go get some solid marks ???. Just kidding!! Cheating is bad — don’t ever do it!

Hope you got the main idea behind the different usages for data structures and how to find the in-order successor and predecessor in a BST.

EDIT: Kudos to Divya Godayal for pointing out a set of major mistakes in the initial draft and also for ensuring that the article flows nicely :) :)