Problem Solving on Binary Trees

Problem solving on binary trees questions are quite common in nowadays interviews for top software companies. Let’s start with the binary tree basics and then we will dive into how to solve the problems.

What is a Binary Tree?

A Binary Tree is a tree whose elements have at most 2 children. We will see what a BST is shortly. So follow with me.

Binary Tree Photo

How to create Binary Tree in Java?

I am writing the code in Java, it wont differ much for C/ C++ or any object oriented language.

public class BinaryTree {
//Here the Tree class is a static inner class
static class Tree{
 int data;
 Tree left;
 Tree right;
 public Tree(int data){
   this.data = data;
   left = null;
   right = null;
 }
}
//Lets create a Tree in main..
public static void main(String[] args) {
  Tree tree = new Tree(2);
  //Left tree from root
  tree.left = new Tree(7);
  tree.left.left = new Tree(2);
  tree.left.right = new Tree(6);
  tree.left.right.left = new Tree(5);
  tree.left.right.right = new Tree(11);
 
  //Right tree from root
  tree.right = new Tree(5);
  tree.right.right = new Tree(9);
  tree.right.right.left = new Tree(4);
 }
}

How to traverse a binary tree?

A binary tree can be traversed, in multiple ways Inorder traversal, postOrder traversal, preOrder traversal, levelOrder traversal and many different ways.
I will discuss here the few, follow me along.

//Left-Node-Right
public void inOrderTraversal(Tree root){
 if(root == null)
   return;
 inOrderTraversal(root.left);
 System.out.print(root.element + " , ");
 inOrderTraversal(root.right);
}

For the above tree, the inOrder traversal will look like this
2->7->5->6->11->2->5->4->9

//Node-Left-Right
public void preOrderTraversal(Tree root){
 if(root == null)
   return;
 System.out.print(root.element + " , ");
 preOrderTraversal(root.left);
 preOrderTraversal(root.right);
}

For the above tree, the preOrderTraversal traversal will look like this
2->7->2->6->5->11->5->9->4

//Left-Right-Node
public void postOrderTraversal(Tree root){
 if(root == null)
   return;
 postOrderTraversal(root.left);
 postOrderTraversal(root.right);
 System.out.print(root.element + " , ");
}

For the above tree, the postOrderTraversal traversal will look like this
2->5->11->6->7->4->9->5->2

//Level Order Traversal or Breadth First
public void levelOrderTraversal(Tree root){
 if(root == null)
   return;
 Queue<Node> queue = new LinkedList<Node>();
 queue.add(root);
 while(!queue.isEmpty()){
   Node tempNode = queue.remove();
   System.out.print(tempNode.element + " , ");
   if(tempNode.left != null)
     queue.add(tempNode.left);
   if(tempNode.right != null)
     queue.add(tempNode.right);
 }
}

For the above tree, the levelOrderTraversal traversal will look like this
2->7->5->6->11->2->5->4->9

How to solve binary tree problems

Approach

Almost all tree problems in general are approached recursively. Hence when given a binary Tree problem, always try reducing the problem to a subtree problem. While doing the above, you will force your mind to think of a recursive solution.
Now one can argue here, why not use an iterative solution. Yes you can definitely use an iterative solution. But in my view for iterative solutions, one has to take care of boundary conditions much more carefully than in a recursive one. Plus recursive solutions are much more cleaner.
However, this is a personal opinion, some might differ to agree.
Now there are basically around 40 questions, in around binary trees, which when practised can give one a hold over the concepts of tree.
But remember this, before you jump write code, you must do it on pen and paper.

I personally do it on white board

white board problem solving photo

Binary trees can be approached either depth first or breadth first. 
Breadth first is the same as level order traversal, where one uses a queue, to traverse the tree.
Depth first approach is using a stack, use a compiler stack or a create a stack, it’s the same. All the primitive well known traversals like PreOrder, PostOrder and Inorder traversal are achieved using the compiler stack.

Order

Now a binary tree has a very defined property that it has 2 children at max. Now searching an element, count of the nodes, its height, predecessor or successor all would have a time complexity of O(n), where n is the number of nodes in the tree.
Since there is no pattern in a binary tree, so naturally one has to traverse all the nodes.
We will see in a few other posts how, in BST, AVL and Red-Black Trees the time complexity can be reduced to O(log n).

Here is the GitHub link for some of the general and most asked problem solving on binary trees.

Binary Trees problem solving
Previous Post

No more post

Binary Trees problem solving
Next Post

No more post

Leave a Reply