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:

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);
    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){
  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){
    n = n.left;
    Node topNode = s.pop(); // already been printed
    topNode = topNode.right;
    while(topNode != null){
      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);
  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){
    n = n.left;
    Node topStackNode = s.pop();
    if(topStackNode.right != null){
      topStackNode = topStackNode.right;
      while(topStackNode != null){
        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);

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){
    if(n.left == null) n = n.right;
    else               n = n.left;
    // 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();
    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){
        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>();
    Node elem = q.remove();
    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>();
    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 + " ");
      if(top.right != null){
        System.out.print(top.right.value + " ");

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>();
  int maxLevel = 1;
    Node top = s.pop();
    int currentLevel = levels.pop();
    maxLevel = Math.max(maxLevel, currentLevel);
    for(Node c : top.getChildren()){
      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>();
  int maxSum = 0;
    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()){
        values.add(c.value + val);
  return maxSum;

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 fail on this 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 ];
  node [shape=circle];
  edge [arrowsize=0.8];
  8 -> 5;
  5 -> 1;
  5 -> 6;
  8 -> 17;
  17 -> 14;
  17 -> 23;

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

Bad tree layout

Bad tree layout

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

Improved tree layout

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("node [shape=circle];\n");
  sb.append("edge [arrowsize=0.8];\n");
  StringBuilder treeContent = getDotTreeContent(new StringBuilder(), t.root, 1);
  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;
Markdown SHA1: 507cc2be2c3e8cd71f653c3f277ad0225f84e1d3