Table of Contents
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:
public class BinTree {
private Node root;
public BinTree (Node r){
root = r;
}
}
public class Node {
int value;
Node left;
Node right;
public Node(int v) {
value = v;
}
}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:
public void insert(int i){
Node newNode = new Node(i);
if(this.root == null) this.root = newNode;
else insertR(root, newNode);
}
private void insertR(Node parent, Node toInsert){
if(toInsert.value <= parent.value){
if(parent.left == null) parent.left = toInsert;
else insertR(parent.left, toInsert);
}
else{
if(parent.right == null) parent.right = toInsert;
else insertR(parent.right, toInsert);
}
}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:
public static void preorderRecursive(BinTree t){
if(t.root != null) preorderRecursiveAux(t.root);
}
private static void preorderRecursiveAux(Node n){
System.out.println(n.value);
if(n.left != null) preorderRecursiveAux(n.left);
if(n.right != null) preorderRecursiveAux(n.right);
}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:
public static void preorderIterative(BinTree t){
if(t.root != null) preorderIterativeAux(t.root);
}
private static void preorderIterativeAux(Node n){
Stack<Node> s = new Stack<Node>();
while(n != null){
System.out.println(n.value);
s.push(n);
n = n.left;
}
while(!s.empty()){
Node topNode = s.pop(); // already been printed
topNode = topNode.right;
while(topNode != null){
System.out.println(topNode.value);
s.push(topNode);
topNode = topNode.left;
}
}
}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:
public static void inorderRecursive(BinTree t){
if(t.root != null) inorderRecursiveAux(t.root);
}
private static void inorderRecursiveAux(Node n){
if(n.left != null) inorderRecursiveAux(n.left);
System.out.println(n.value);
if(n.right != null) inorderRecursiveAux(n.right);
}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:
public static void inorderIterative(BinTree t){
if(t.root != null) inorderIterative(t.root);
}
private static void inorderIterative(Node n){
Stack<Node> s = new Stack<Node>();
while(n != null){
s.push(n);
n = n.left;
}
while(!s.empty()){
Node topStackNode = s.pop();
System.out.println(topStackNode.value);
if(topStackNode.right != null){
topStackNode = topStackNode.right;
while(topStackNode != null){
s.push(topStackNode);
topStackNode = topStackNode.left;
}
}
}
}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.
public static void postorderRecursive(BinTree t){
if(t.root != null) postorderRecursiveAux(t.root);
}
private static void postorderRecursiveAux(Node n){
if(n.left != null) postorderRecursiveAux(n.left);
if(n.right != null) postorderRecursiveAux(n.right);
System.out.println(n.value);
}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.
public static void postorderIterative(BinTree t){
if(t.root != null) postorderIterativeAux(t.root);
}
private static void postorderIterativeAux(Node n){
Stack<Node> s = new Stack<Node>();
// Go left while adding to the stack. When can't go
// anymore, go right, and then left again and repeat,
// adding to the stack the whole time.
while(n != null){
s.push(n);
if(n.left == null) n = n.right;
else n = n.left;
}
while(!s.empty()){
// Get the top node, print it out, and get its parent.
// The parent must be the next element on the stack
Node topNode = s.pop();
System.out.println(topNode.value);
Node topNodeParent = null;
if(!s.empty()) topNodeParent = s.peek();
// If there is a parent, and it's left subtree is unexplored,
// go explore it.
if(topNodeParent != null && topNodeParent.right != topNode){
Node tempNode = topNodeParent.right;
// Same process as in the beginning.
while(tempNode != null){
s.push(tempNode);
if(tempNode.left == null) tempNode = tempNode.right;
else tempNode = tempNode.left;
}
}
}
}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:
public static void levelOrder(BinTree t){
if(t.root != null) levelOrderAux(t.root);
}
private static void levelOrderAux(Node n){
Queue<Node> q = new LinkedList<Node>();
q.add(n);
while(!q.isEmpty()){
Node elem = q.remove();
System.out.println(elem.value);
if(elem.left != null) q.add(elem.left);
if(elem.right != null) q.add(elem.right);
}
}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:
public static void levelOrderDelim(BinTree t){
if(t.root != null) levelOrderDelimAux(t.root);
}
private static void levelOrderDelimAux(Node n){
Queue<Node> q = new LinkedList<Node>();
System.out.println(n.value);
q.add(n);
while(!q.isEmpty()){
int k = q.size();
while(k > 0){ // Process elements on the same level
Node top = q.remove();
if(top.left != null){
System.out.print(top.left.value + " ");
q.add(top.left);
}
if(top.right != null){
System.out.print(top.right.value + " ");
q.add(top.right);
}
k--;
}
System.out.print("\n");
}
}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:
public static int maxHeightRecursive(BinTree t){
if(t.root == null) return -1;
else return maxHeightAux(t.root, 0);
}
private static int maxHeightAux(Node n, int height){
if(n == null) return height;
int lHeight = maxHeightAux(n.left, height + 1);
int rHeight = maxHeightAux(n.right, height + 1);
return Math.max(lHeight, rHeight);
}The above code keeps the current height as a function parameter. Alternatively, you could opt to define it as:
private static int maxHeightAux2(Node n){
int lHeight = 0;
int rHeight = 0;
if(n.left != null) lHeight = maxHeightAux2(n.left);
if(n.right != null) rHeight = maxHeightAux2(n.right);
return Math.max(lHeight,rHeight) + 1;
}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.
private static int maxHeightIterativeAux(Node n){
Stack<Node> s = new Stack<Node>();
Stack<Integer> levels = new Stack<Integer>();
s.add(n);
levels.add(1);
int maxLevel = 1;
while(!s.empty()){
Node top = s.pop();
int currentLevel = levels.pop();
maxLevel = Math.max(maxLevel, currentLevel);
for(Node c : top.getChildren()){
s.push(c);
levels.push(currentLevel + 1);
}
}
return maxLevel;
}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.
public static int maxSumR(BinTree t){
if(t.root == null) return 0;
else return maxSumRAux(t.root);
}
private static int maxSumRAux(Node n){
if(n == null) return 0;
if(n.left == null && n.right == null) return n.value;
return n.value + Math.max(maxSumRAux(n.left),maxSumRAux(n.right));
}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:
public static int maxSum(BinTree t){
if(t.root == null) return 0;
Stack<Node> s = new Stack<Node>();
Stack<Integer> values = new Stack<Integer>();
s.add(t.root);
values.add(t.root.value);
int maxSum = 0;
while(!s.empty()){
Node top = s.pop();
int val = values.pop();
if(top.left == null && top.right == null){ // if it's a leaf node
maxSum = Math.max(maxSum, val);
} else{
for(Node c : top.getChildren()){
s.add(c);
values.add(c.value + val);
}
}
}
return maxSum;
}6 Validating a BST
Provide a function that given a binary tree returns
trueif the tree is a BST andfalseotherwise.
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 fail on this 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:
public static boolean validateBST(BinTree t){
if(t.root == null) return true; // an empty tree is a BST
else return validateBSTAux(t.root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
private static boolean validateBSTAux(Node n, int minBound, int maxBound){
if(n.value < minBound || n.value > maxBound) return false;
boolean lTreeOK = true;
boolean rTreeOK = true;
if(n.left != null) lTreeOK = validateBSTAux(n.left, minBound, n.value);
if(n.right != null) rTreeOK = validateBSTAux(n.right, n.value+1, maxBound);
return lTreeOK && rTreeOK;
}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:
digraph G {
graph [ dpi = 150 ];
nodesep=0.3;
ranksep=0.2;
margin=0.1;
node [shape=circle];
edge [arrowsize=0.8];
8 -> 5;
5 -> 1;
5 -> 6;
8 -> 17;
17 -> 14;
17 -> 23;
}Save the above as tree.dot. Running dot tree.dot | neato -n -Tpng -o treeBadLayout.png produces the following:
Bad tree layout
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:
Improved tree layout
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:
public static String getDotFile(BinTree t){
StringBuilder sb = new StringBuilder();
sb.append("digraph G {\n");
sb.append("graph [ dpi = 150 ]\n");
sb.append("nodesep=0.3;\n");
sb.append("ranksep=0.2;\n");
sb.append("margin=0.1;\n");
sb.append("node [shape=circle];\n");
sb.append("edge [arrowsize=0.8];\n");
StringBuilder treeContent = getDotTreeContent(new StringBuilder(), t.root, 1);
sb.append(treeContent);
sb.append("}");
return sb.toString();
}
// Pre: N is not null.
// This won't work for larger unbalanced trees (int overflow), but then again you probably
// wouldn't be displaying them anyway, so this is good enough for now.
private static StringBuilder getDotTreeContent(StringBuilder sb, Node n, int i){
sb.append(String.format("node%d [label=\"%d\"];\n", i, n.value));
int lChild = 2*i;
int rChild = 2*i + 1;
if(n.left != null){
sb.append(String.format("node%d -> node%d;\n", i, lChild));
getDotTreeContent(sb, n.left, lChild);
}
if(n.right != null){
sb.append(String.format("node%d -> node%d;\n", i, rChild));
getDotTreeContent(sb, n.right, rChild);
}
return sb;
}