# Binary Trees

#### Posted on November 15, 2013

##### Last updated on January 25, 2014

In this article I will cover various algorithms pertaining to binary trees. This can be useful if you are preparing for some interviews (I try to cover popular questions), or need to brush up your knowledge on binary trees.

# 1 Definition

A binary tree is a data structure that has a node with a value, and pointers to two other data structures - a left tree, and a right tree, both of which are themselves binary trees. A binary search tree is a binary tree such that for every node $$n$$, all elements in the left subtree are smaller than or equal to the value of $$n$$, and all elements in the right subtree are greater than the value of $$n$$.

Here is how we could implement a simple Binary Tree class in Java:

A binary tree is defined by its root element, which is a Node. Each node then has a value, and pointers to its left and right subtrees.

# 2 Insertion Algorithm

Given a binary search tree and an integer, insert the integer into the binary search tree, such that the result is still a binary search tree.

We need to traverse the tree to find the insertion point for the new element. Start at the root, and keep traversing the tree as if to find where the element, if it was already in the tree, would be located. Once you get to an empty leaf during this traversal, this is precisely where you should insert the new element. In Java:

# 3 Traversal Algorithms

Given a binary tree, print out its elements

Looks simple. We have a couple of options to do this. There are four well known tree traversal methods: preorder, inorder, postorder, and level order. I will explain them in the relevant subsections. Firstly, notice that all our algorithms must be $$O(n)$$ in time, since we have to necessarily visit every element of an $$n$$-element binary tree. What can differ though is the space complexity of our solutions. A recursive formulation, while the simplest, might quickly get us a stack overflow exception due to size of the call stack. Without using recursion, we can keep all the data we need on the much larger heap.

In the following sections, I’ll go through how to implement all four methods both recursively and iteratively. We will simply print out the node’s value when visiting it, although that step can obviously be adapted, for example to return list of the nodes visited in the desired order.

## 3.1 Preorder

A preorder traversal for a binary tree $$t$$ means we first visit the root node, and then recursively visit the left, and then recursively visit the right subtree.

### 3.1.1 Recursive

Very easy to implement. Java:

### 3.1.2 Iterative

The iterative versions of all the algorithms are more challenging than the simple recursive versions. The core idea is to use a stack to manager your program as it would be run if it would be ran recursively. Except now you own the stack and it’s on the heap, giving you more space to work with than the call stack.

A preorder traversal will first visit the root, and then continually visit left children until it can no longer visit left children. Then, it will go to visit the right node of the last element visited, and again go on a spree visiting the left children until there are no more left. This continues until there are no elements left to visit.

In Java:

## 3.2 Inorder

An inorder traversal for a binary tree $$t$$ means we first recursively visit the left tree, then the root, and then recursively visit the right tree.

### 3.2.1 Recursive

Java implementation:

### 3.2.2 Iterative

Again, you have to figure out how to simulate the recursion using a normal stack on the heap, and while loops. First, notice that an inorder traversal will start off with the smallest element if its traversing a binary search tree. Indeed, an inorder traversal of a binary search tree is a sort. The smallest element will be the leftmost element. Then, the next smallest element, will be the leftmost element of the right child of the element we’ve just visited. All this can be easily modelled with a stack. Here is the Java code:

## 3.3 Postorder

A postorder traversal for a binary tree $$t$$ means we first recursively visit the left tree, then recursively visit the right tree, and then finally visit the root of the tree.

### 3.3.1 Recursive

Again, the recursive implementation is dead simple.

### 3.3.2 Iterative

The iterative version is non-trivial. Have a think about it and try doing it yourself before continuing.

The issue is that, before visiting anything, we have to in a way simulate two consecutive recursions, one for each subtree. The key operation we need is to be able to get the deepest and leftmost element in any subtree we are currently traversing. This will be the first element that a post-order traversal will print out. Then, we have to simulate backtracking, by visiting the parent, and performing the same operation on the right subtree (if it hasn’t been visited already). It’s better if you actually first attempt to do it yourself, and then have a look at the working Java code below.

## 3.4 Level Order

Level order prints out nodes level by level, as you see them when viewed literally as tree with levels.

### 3.4.1 Level Order without level delimiters

If you don’t need to see where each next level starts, the problem is simple. It’s a breadth-first traversal, for which we can use another well known data structure: the queue. In Java:

### 3.4.2 Level order with delimiters

Maybe you also need to print a newline whenever you move on to the next level. This is a bit more tricky:

# 4 Tree Depth

Given a binary tree, find its maximum depth; that is, find the number of levels in the tree. A tree with only one node has depth 1, etc.

## 4.1 Recursive solution

We can solve this easily recursively. The depth of a tree rooted at $$n$$ is $$1 + \operatorname{depth}(n.left) + \operatorname{depth}(n.right)$$. This translates to the following Java code:

The above code keeps the current height as a function parameter. Alternatively, you could opt to define it as:

This is closer to the original specification above, but accomplishes the same thing.

## 4.2 Iterative version

We can adapt any of the iterative traversal methods to give us the maximal depth. While traversing, simply keep account of the maximal depth encountered so far. For practice, we will traverse the tree using Depth First Search, keeping account of the level using an additional stack.

Note that I added a helper method getChildren, that given a node, returns all it’s children. This is so that our code will generalize for an arbitrary tree.

# 5 Maximal sum from root to leaf

Given a binary tree with integers, find the maximal sum from the root to a leaf.

I saw this somewhere as an interview question. It’s easily expressed recursively:

## 5.1 Recursively

As usual, the recursive code pretty much follows from the definition.

## 5.2 Iteratively

Even though it’s simple, such recursive traversals are not good for large problem instances. To solve this iteratively, we can use DFS again:

# 6 Validating a BST

Provide a function that given a binary tree returns true if the tree is a BST and false otherwise.

Now you might think that something akin to this could work: For a node $$n$$, check if the value of the left child is smaller than or equal to than the value of $$n$$, check if the value of the right child is greater than the value of $$n$$, and do this recursively for all the children.

There is a problem with this though. Consider the following tree:

The presented algorithm will incorrectly classify the tree as a BST. The issue is that even though $$50 > 5$$, we also have that $$50 > 8$$ which means $$50$$ is in the wrong branch of the tree.

A modified algorithm works as follows: For every subtree being visited, keep a set of bounds $$[a,b]$$ that keep track of the allowed values on the current path. If any visited subtree fails this test, then the tree being traversed is not a BST. Here is a correct (for trees storing integers) BST validation method:

# 7 Visualizing a tree with dot/Graphviz

For this post, I needed to somehow visualize the trees. There already is graphviz/dot for all kinds of fancy graph visualizations, except by default the tree layout won’t give us a nice looking binary tree. There is a solution though: you will need to have dot, gvpr, and neato, which all should come preinstalled with graphviz. You will also need the following file tree.gv to pass to gvpr. The script is not mine, and I can’t find anymore where I originally found it. Then, take for example this very simple binary tree:

Save the above as tree.dot. Running dot tree.dot | neato -n -Tpng -o treeBadLayout.png produces the following:

Now, using the above script, we can run dot tree.dot | gvpr -c -f tree.gv | neato -n -Tpng -o treeGoodLayout.png and get back the following improved tree:

## 7.1 Generating the dot file in Java

Generating the dot file is just a simple traversal. If all our nodes are unique, then we have no issues. But if we have more than one node with the same value, the simple approach of using the value as a node identifier for dot will not work, since dot won’t know which node we are referring to. To do this, each node has to get a unique identifier. Here is one solution, using the fact that given some node with index $$i$$, we can call its left child $$2i$$ and its right child $$2i + 1$$, and every node will have a unique identifier. This works well enough for any kind of tree you would probably need to display on the screen. Here is Java implementation: