Binary Tree

11 Binary Tree problems which can be solved by just 1 Algo!

There is an interesting resemblance between various Binary Tree problems and one solution.

The Problem can be –

1. Print all the nodes of a BT level by level
2. Or Reverse Level Order Traversal
3. Or No. of levels in a BT.
4. Or Height / Max depth of a BT.
5. Or Sum of all node in a BT.
6. Or Sum of individual levels in a BT
7. Or Find max node value in a BT
8. Or Search a given value in a BT
9. Or Add a new node in a BT
10. Or Compare if two BT’s are identical
11. Or Compare If two tree are mirror

And the solution will be –

1.     Level Order traversal + Some extra logic as per the problem

Now How we can do it…

Here is code snippet of functions utilising the level order traversal concept to solve the above problems, the code is in C# but you can modify and convert it any other language of your choice very easily and it does not use any specifics here (However some extra things might be required such as you may need to import queue module in Python as it is not provided by default etc.)

First and foremost The level order traversal itself –

My node class will look like as below

public class Node
{
public Object data;
public Node left;
public Node right;
}

1. Level order traversal

public void levelordertraversal(Node root)
{
     Queue<Node> myQ = new Queue<Node>();
     myQ.Enqueue(root);
     Node current = null;
     if (root == null)
          return;

     while (myQ.Count != 0)
    {
          current = myQ.Dequeue();
          Console.Write(current.data.ToString() + ” “);
          if (current.left != null)
          {
               myQ.Enqueue(current.left);
         }
        if (current.right != null)
        {
              myQ.Enqueue(current.right);
        }
   }
}

2. Level Order Traversal Right Associativity

public void levelordertraversalRight(Node root)
{
     Queue<Node> myQ = new Queue<Node>();
     myQ.Enqueue(root);
     Node current = null;
     if (root == null)
          return;

     while (myQ.Count != 0)
     {
          current = myQ.Dequeue();
          Console.Write(current.data.ToString() + ” “);
          if (current.right != null)
          {
               myQ.Enqueue(current.right);
         }
         if (current.left != null)
         {
               myQ.Enqueue(current.left);
        }
    }
}

3. Reverse level order traversal

public void Revlevelordertraversal(Node root)
{
Queue<Node> myQ = new Queue<Node>();
myQ.Enqueue(root);
Stack<Node> mystack = new Stack<Node>();
Node current = null;
if (root == null)
return;

while (myQ.Count != 0)
{
current = myQ.Dequeue();
mystack.Push(current);
if (current.left != null)
{
myQ.Enqueue(current.left);
}
if (current.right != null)
{
myQ.Enqueue(current.right);
}
}

while (mystack.Count != 0)
{
Console.Write(mystack.Pop().data.ToString() + ” “);
}
}

4. Height of a BT

public int HeightofTree(Node root)
{
Queue<Node> myQ = new Queue<Node>();
myQ.Enqueue(root);
Node current = null;
int noofnode = 0;
int height = 0;

if (root == null)
return 0;

while (true)
{
noofnode = myQ.Count;

if (noofnode == 0)
return height -1;
else
height = height + 1;

while (noofnode > 0)
{
current = myQ.Dequeue();
if (current.right != null)
{
myQ.Enqueue(current.left);
}
if (current.left != null)
{
myQ.Enqueue(current.right);
}

noofnode–;
}
}
}

5. # of levels in a BT

public int NoOfLevelofTree(Node root)
{
Queue<Node> myQ = new Queue<Node>();
myQ.Enqueue(root);
Node current = null;
int noofnode = 0;
int level = 0;

if (root == null)
return 0;

while (true)
{
noofnode = myQ.Count;

if (noofnode == 0)
return level;
else
level = level + 1;

while (noofnode > 0)
{
current = myQ.Dequeue();
if (current.right != null)
{
myQ.Enqueue(current.left);
}
if (current.left != null)
{
myQ.Enqueue(current.right);
}

noofnode–;
}
}
}

6.. Sum of all node of a BT

public void SumofallNodes(Node root)
{
Queue<Node> myQ = new Queue<Node>();
myQ.Enqueue(root);
Node current = null;
if (root == null)
return;
int sum = 0;
while (myQ.Count != 0)
{
current = myQ.Dequeue();
sum = sum + Convert.ToInt32(current.data);
if (current.left != null)
{
myQ.Enqueue(current.left);
}
if (current.right != null)
{
myQ.Enqueue(current.right);
}
}

Console.Write(sum.ToString());
}

7. Level by level sum of a BT

public int LevelSum(Node root)
{
Queue<Node> myQ = new Queue<Node>();
myQ.Enqueue(root);
Node current = null;
int noofnode = 0;
int level = 0;
int sum = 0;
if (root == null)
return 0;

while (true)
{
noofnode = myQ.Count;
sum = 0;

if (noofnode == 0)
return level;
else
level = level + 1;

while (noofnode > 0)
{
current = myQ.Dequeue();
if (current.right != null)
{
myQ.Enqueue(current.left);
}
if (current.left != null)
{
myQ.Enqueue(current.right);
}
sum = sum + Convert.ToInt32(current.data);
noofnode–;
}
//Print the sum at each level
Console.Write(“Sum at level – ” + level + ” is ” + sum.ToString() + “\n”);
}
}

8. Max node value in a BT

public int MaxNodeValue(Node root)
{
Queue<Node> myQ = new Queue<Node>();
myQ.Enqueue(root);
Node current = null;
int max = int.MinValue;

if (root == null)
return 0 ;

while (myQ.Count != 0)
{
current = myQ.Dequeue();
//Compare the current node value with
if (max < Convert.ToInt32(current.data))
max = Convert.ToInt32(current.data);
//Travese the tree level by level for all nodes
if (current.left != null)
{
myQ.Enqueue(current.left);
}
if (current.right != null)
{
myQ.Enqueue(current.right);
}
}

return max;
}

9. Search a given node in BT

public bool SearchNodeValue(Node root, int data)
{
Queue<Node> myQ = new Queue<Node>();
myQ.Enqueue(root);
Node current = null;

if (root == null)
return false;

while (myQ.Count != 0)
{
current = myQ.Dequeue();
//Compare the current node value with
if (data == Convert.ToInt32(current.data))
return true;
//Travese the tree level by level for all nodes
if (current.left != null)
{
myQ.Enqueue(current.left);
}
if (current.right != null)
{
myQ.Enqueue(current.right);
}
}

return false;
}

10. compare if two tree are identical

public bool CompareTree(Node root1, Node root2)
{
Queue<Node> myQ1 = new Queue<Node>();
Queue<Node> myQ2 = new Queue<Node>();
myQ1.Enqueue(root1);
myQ2.Enqueue(root2);
Node current1 = null;
Node current2 = null;

if (root1 == null)
return false;
else if (root2 == null)
return false;

while (true)
{
if (myQ1.Count == 0 && myQ2.Count != 0)
return false;
else if (myQ1.Count != 0 && myQ2.Count == 0)
return false;
else if (myQ1.Count == 0 && myQ2.Count == 0)
return true;

current1 = myQ1.Dequeue();
current2 = myQ2.Dequeue();
//Compare the current node value with
if (Convert.ToInt32(current2.data) != Convert.ToInt32(current2.data))
return false;
//Travese the tree1 level by level for all nodes
if (current1.left != null)
{
myQ1.Enqueue(current1.left);
}
if (current1.right != null)
{
myQ1.Enqueue(current1.right);
}
//Travese the tree2 level by level for all nodes
if (current2.left != null)
{
myQ2.Enqueue(current2.left);
}
if (current2.right != null)
{
myQ2.Enqueue(current2.right);
}

}
}

11. compare if two tree are mirror image of each other

public bool MirrorTree(Node root1, Node root2)
{
Queue<Node> myQ1 = new Queue<Node>();
Queue<Node> myQ2 = new Queue<Node>();
myQ1.Enqueue(root1);
myQ2.Enqueue(root2);
Node current1 = null;
Node current2 = null;

if (root1 == null)
return false;
else if (root2 == null)
return false;

while (true)
{
if (myQ1.Count == 0 && myQ2.Count != 0)
return false;
else if (myQ1.Count != 0 && myQ2.Count == 0)
return false;
else if (myQ1.Count == 0 && myQ2.Count == 0)
return true;

current1 = myQ1.Dequeue();
current2 = myQ2.Dequeue();
//Compare the current node value with
if (Convert.ToInt32(current2.data) != Convert.ToInt32(current2.data))
return false;
//Travese the tree1 level by level for all nodes
if (current1.left != null)
{
myQ1.Enqueue(current1.left);
}
if (current1.right != null)
{
myQ1.Enqueue(current1.right);
}
//Travese the tree2 level by level for all nodes – Right associative
if (current2.left != null)
{
myQ2.Enqueue(current2.right);
}
if (current2.right != null)
{
myQ2.Enqueue(current2.left);
}

}
}

12. Adding a node to binary tree

public Node AddNode(object data)
{
if (root == null)
{
Node NewNode = new Node();
NewNode.data = data;
NewNode.left = null;
NewNode.right = null;
root = NewNode;
}
else
{
//Level order traversal
Queue <Node> Q = new Queue<Node>();
Q.Enqueue(root);
Node current;
while (Q.Count != 0)
{
current = Q.Dequeue();
if (data == current.data)
{
return root;
}
if (current.left != null)
{
Q.Enqueue(current.left);
}
else
{
Node Newchild = new Node();
Newchild.data = data;
Newchild.left = null;
Newchild.right = null;
current.left = Newchild;
return root;
}
if (current.right != null)
{
Q.Enqueue(current.right);
}
else
{
Node Newchild = new Node();
Newchild.data = data;
Newchild.left = null;
Newchild.right = null;
current.right = Newchild;
return root;
}
}

}

return root;
}

Driver Program

class Program
{
     //Driver function
     static void Main(string[] args)
     {
          //Create a Tree first, something as below
          //            1
          //           / \
          //          2 3
          //        / \ / \
          //      4 5 6 7
          Btree mytree = new Btree();
          mytree.AddNode(1);
          mytree.AddNode(2);
          mytree.AddNode(3);
          mytree.AddNode(4);
          mytree.AddNode(5);
          mytree.AddNode(6);
          mytree.AddNode(7);
          //1. Level order traversal – mytree.levelordertraversal(mytree.root); O/P = 1 2 3 4 5 6 7
          //2. Right LOT  – mytree.levelordertraversalRight(mytree.root); O/P = 1 3 2 7 6 5 4
          //3. Pre Order – mytree.preorder(mytree.root); O/P = 1 2 4 5 3 6 7
          //4. Post Order – mytree.postorder(mytree.root); O/P = 4 5 2 6 7 3 1
          //5. Sum of all nodes – mytree.SumofallNodes(mytree.root); O/P = 28
          //6. Sum of nodes at each level – mytree.LevelSum(mytree.root); O/P = Sum at level 1           – 1, Sum at level 2 – 5, Sum at level 3 – 22
          //7. # of levels – int level = mytree.NoOfLevelofTree(mytree.root); O/P = 3
          //8. Reverse level order traversal mytree.Revlevelordertraversal(mytree.root); O/P – 7           6 5 4 3 2 1
          //9. Height of the BT int height = mytree.HeightofTree(mytree.root); O/P = 2
          //10. Max node value mytree.MaxNodeValue(mytree.root); O/P = 7
          //11. Search a node with value mytree.SearchNodeValue(mytree.root, 5); O/P = True                     for the given value else false if value does not exist
          //Create another tree for comparision – identical
          /*Btree mytree1 = new Btree();
          mytree1.AddNode(1);
          mytree1.AddNode(2);
          mytree1.AddNode(3);
          mytree1.AddNode(4);
          mytree1.AddNode(5);
          mytree1.AddNode(6);
          mytree1.AddNode(7); */
          //12. check if two tree are identical mytree.CompareTree(mytree.root, mytree1.root);           O/P – True or false
          //Create another tree for comparision – Mirror
          /*Btree mytree1 = new Btree();
          mytree1.AddNode(1);
          mytree1.AddNode(3);
          mytree1.AddNode(2);
          mytree1.AddNode(7);
          mytree1.AddNode(6);
          mytree1.AddNode(5);
          mytree1.AddNode(4); */
          //13. check if two tree are mirror mytree.MirrorTree(mytree.root, mytree1.root); O/P –           True or false
          Console.Read();
      }
}