algomaster, Author at Algo Tutor

0

Find height of binary tree

Posted on June 3, 2015 by algomaster

Problem:

Calculate height of a binary tree:

Logic:

In binary tree left subtree and right subtree are also binary trees. We will calculate height of each subtree and will select maximum of both. 1 is added to maximum height of tree to add distance of root from a subtree. Recursive method call was made for each node till node is null to get height of a tree.

int HeightOfTree(Node root)
{
  if (root == null)
   return -1;
  return 1 + Math.Max(HeightOfTree(root.Left),HeightOfTree(root.right));
}

1

2

3

4

5

6

int HeightOfTree(Node root)

{

if (root == null)

return -1;

return 1 + Math.Max(HeightOfTree(root.Left),HeightOfTree(root.right));

}

If root is null (for left and right child of leaf node) we are returning value -1 because in a final result we are adding 1 . If we return 0 instead of -1 then for leaf node we will get height as 1 (o+1) instead of 0 which is wrong. So to balance 1 we are returning -1 in if condition.

If you want to understand recursive call and how we will get correct output as result, you can refer this and try to trace above function in same way.

Also if you are new to recursion, you can check my article on recursion.

To calculate height all nodes of tree are visited, so complexity of function will be O( n)

0

Sum of all nodes in Binary tree

Posted on June 3, 2015 by algomaster

Problem:

Calculate sum of all nodes in a binary tree.

int SumOfNodes(Node rt)
{
  if (rt == null)
    return 0;
  return rt.value + SumOfNodes(rt.left) + SumOfNodes(rt.right);
}

1

2

3

4

5

6

int SumOfNodes(Node rt)

{

if (rt == null)

return 0;

return rt.value + SumOfNodes(rt.left) + SumOfNodes(rt.right);

}

You refer following image to understand function calls in above recursive method.

We need to visit all nodes, so time complexity will be O( n)

0

Binary Trees

Posted on June 2, 2015 by algomaster

Lets discuss binary tree concepts and few basic frequently asked programming questions related to it.

Binary tree is tree in which each node can have at the most two children. This means each node can have 0 children (leaf node) , 1 children or two children. Generally referred as left child and right child. In terms, both left sub-tree and right sub-tree are also binary trees.

Complete Binary tree: A binary tree in which all the levels are complete filled except last level which is filled from left to right.

Balanced Binary tree: A binary tree in which difference between the height of left sub-tree and right sub-tree is 0 or 1

Perfect or Full Binary tree: A binary tree in which each node have exactly 0 or 2 nodes.

A complete binary tree and a perfect binary tree is always going to be balanced binary tree.

Height of Binary tree:

Lets consider ‘n’ total number of nodes in balanced binary tree and ‘l_k‘ is the numbers nodes at level ‘l’.

So, for k = 0 -> l₀ = 1 (root node)

for k = 1 -> l₁ = 2 (second level)

for k = 2 -> l₂ = 4 (second level) and so on..

This means each node will have twice number of nodes from its previous level. Total number of nodes can be represent using this concept as:

2⁰+ 2¹ + 2²+2³+2⁴+……+ 2^h= n here h is a height of tree

So, 2^h+1 -1 = n (for understanding, 2⁰⁺¹ -1 -> 2¹ – 1 =1 for level 0 and so on..for each level we can compute)

Now, we will calculate hight of balanced binary tree if has n nodes using above expression:

2^h+1= n+1

h+1 = lg(n+1)

h= lg(n+1) – 1

By l’Hopital’s rule this expression follows as: lg(n+1) – 1 = lg(n)

So, h = lg(n)

In binary tree, a minimum height of tree for ‘n’ nodes can be |_lg(n)_| (ceiling function) and maximum height can be (n-1).

A perfect binary tree of height h has 2^hleaf nodes in terms of height and has (n+1)/2 leaf nodes in terms of ‘n’.

Tree Traversal:

Traversal means visiting each node of a tree. Linear data structure like array, we traverse it in one direction starting from 0 index to last index of array. However, tree can be traversed in different ways.

Level Order Traversal: This is also known as breadth first traversal. Every node on a level before going to a lower level.

Depth First Traversal: This traversal can be done in three ways, In-order, Pre-order and Post-order.

Inorder traversal: <left><root><right>

1. Traverse left sub tree.

2. Print data in root.

3. Traverse right sub tree.

Inorder traversal is used in binary search tree we get numbers sorted in sorted ascending order.

Preorder traversal: <root><left><right>

1. Print data in root.

2. Traverse left sub tree.

3. Traverse right sub tree.

By using preorder traversal we can make a copy of a tree.

Postorder traversal: <left><right><root>

1. Traverse left sub tree.

2. Traverse right sub tree.

3. Print data in root.

Postorder traversal is used when we want to delete a tree as we visit parent node after visiting its children.

Note: To remember traversals simple method is to remember position of root with respect to prefix of name of traversal.

Implementation of traversals:

Inorder traversal:

void InOrderTraversal(Node rt)
{
  if (rt == null)
    return;
  else
    {
      InOrderTraversal(rt.left);
      Console.Write(" " + rt.value);
      InOrderTraversal(rt.right);
    }
}

1

2

3

4

5

6

7

8

9

10

11

void InOrderTraversal(Node rt)

{

if (rt == null)

return;

else

{

InOrderTraversal(rt.left);

Console.Write(" " + rt.value);

InOrderTraversal(rt.right);

}

Preorder traversal:

void PreOrderTraversal(Node rt)
{
  if (rt == null)
    return;
  else
   {
     Console.Write(" " + rt.value);
     PreOrderTraversal(rt.left);
     PreOrderTraversal(rt.right);
   }
}

1

2

3

4

5

6

7

8

9

10

11

void PreOrderTraversal(Node rt)

{

if (rt == null)

return;

else

{

Console.Write(" " + rt.value);

PreOrderTraversal(rt.left);

PreOrderTraversal(rt.right);

}

Postorder traversal:

void PostOrderTraversal(Node rt)
{
  if (rt == null)
   return;
  else
   {
     PostOrderTraversal(rt.left);
     PostOrderTraversal(rt.right);
     Console.Write(" " + rt.value);
   }
}

1

2

3

4

5

6

7

8

9

10

11

void PostOrderTraversal(Node rt)

{

if (rt == null)

return;

else

{

PostOrderTraversal(rt.left);

PostOrderTraversal(rt.right);

Console.Write(" " + rt.value);

}

In each traversal every node of a tree is visited so time complexity for tree traversal in O(n).

You can find more coding questions and solutions here.

Lets discuss about binary search tree in next session..

0

Trees

Posted on June 2, 2015 by algomaster

Hi guys, today I am going to discuss trees. We are going to discuss basic concepts of tree data structure before we start discussion about binary trees.

Tree:

Tree is a abstract data structure used to stored data in hierarchical order.

In simple words imagine a diagram showing family members of your family showing relationships like parent-children, grandparents. This diagram is in term a ‘tree data structure’. As you can imagine, its difficult to maintain such type of orders in linear data structure (array, linked list etc.) tree data structure is require.

Basic difference between graph and tree is there are no loops or circles in trees, so each element (referred as node) of tree can be accessed by accessing unique path.

Tree is defined as a binary tree, ternary tree …k-ary depending on maximum number of children a parent element can have.

Tree Terminology:

Root: The topmost node of a tree with no parent.

Leaf Node: Nodes of tree with no children.

Path: Sequence of nodes connected with edges.

Length of path: Number of edges connecting nodes between that path.

Height of node: Longest path from node that node to leaves.

Height of tree: Longest path from root and a leaf.

Depth of node: Distance(number of edges) of that node from root. So for ‘root’ depth=0

and height can be considered as maximum depth of all nodes.

Degree of node: Number of direct children of that node.

Considering these tree terminologies one can say:

-In tree each node can have at the most one parent.

-Each node can be traversed from a root node.

-Each node of a tree can be considered a sub-tree. This property of trees is used to implement trees recursively.

Lets discuss about binary trees in next session…

0

Bubble Sort

Posted on May 31, 2015 by algomaster

Lets discuss Bubble Sort today.

Problem : Given a list of integers in random order, arrange them in either ascending or descending order.

For example consider this list of integers : 4 2 8 1 6 then output should be 1 2 4 6 8 or 8 6 4 2 1 .

There are many sorting algorithms which we can use to solve above problem. But lets start with basic simple and easiest algorithm of sorting i.e. Bubble Sort.

Logic

In Bubble sort for ascending order,as the name suggests we will bubble out the largest number to last position (i.e its correct position in sorted array) in the array. And after that we will repeat the same procedure for the rest of the array until all the numbers are at their correct position.

So how do we bubble out largest number ?

We compare adjacent elements with each other and if the number on left side is greater than the number of right side we swap them. So at the end we have the largest number at the end.

Lets take an example :

Implementation: To sort numbers in ascending order

void BubbleSort(in[] input)
{
  for(int j = input.Length - 1; j > 0; j--)
  {
    for(in i = 0; i < j; i++)
    {
       if(input[i] > input[i+1])
       {
          int temp = input[i];
          input[i] = input[i + 1];
          input[i + 1] = temp;
        }
     }
   }
  Console.WriteLine("Numbers sorted in ascending order: ");
  for(int n = 0; n < input.Length; i++)
    Console.Write(+input[n] + " ");
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

void BubbleSort(in[] input)

{

for(int j = input.Length - 1; j > 0; j--)

{

for(in i = 0; i < j; i++)

{

if(input[i] > input[i+1])

{

int temp = input[i];

input[i] = input[i + 1];

input[i + 1] = temp;

}

Console.WriteLine("Numbers sorted in ascending order: ");

for(int n = 0; n < input.Length; i++)

Console.Write(+input[n] + " ");

}

Analysis:

In this sort, on every pass we will bubble out the largest element from the array to its correct position (i.e. last) this takes O(n) time and we repeat this for every element in array.

After we shift the first largest element to its correct position we reduce the array size by 1.

So, to place 1st element at it’s correct position , number of operations required is : n-1

to place 2nd element at it’s correct position, number of operations required is: n-2 and so on…

So, to sort ‘n’ elements total number of operations required are : (n-1) + (n-2) + (n-3) + …+1 , which is n(n+1)/2. After ignoring constants , result is n². Therefore time complexity of bubble sort in O(n²). Also the number of swaps in bubble sort will be n² in worst case !

Highlights:

-Bubble out the largest element to end by swapping adjacent elements

-Time Complexity O(n²).

-Space Complexity O(1) or constant.

-Number of swaps in worst case is n²

-Bubble sort is Stable sort i.e. it maintains the relative order of elements.

2

Stopwatch Timer App Windows Phone

Posted on January 26, 2015 by algomaster

Let’s implement a very simple Stopwatch Timer app today.

We will implement following features in our Stopwatch app :

1. Show Timer

2. Pause Timer

3. Stop / Reset Timer.

UI for our App :

 <Grid>
        <StackPanel>
            <TextBlock HorizontalAlignment="Center" x:Name="StopwatchText" Text="0 : 0 : 0" FontSize="50" Foreground="White"/>
            <StackPanel Orientation="Horizontal" HorizontalAlignment="Center">
                <Button x:Name="Start" Content="Start" Click="Start_Click"/>
                <Button x:Name="Pause" Content="Pause" Click="Pause_Click"  Margin="5,0,0,0"/>
                <Button x:Name="Stop" Content="Stop" Click="Stop_Click" Margin="5,0,0,0" />
            </StackPanel>
        </StackPanel>
    </Grid>

1

2

3

4

5

6

7

8

9

10

<Grid>

</StackPanel>

</Grid>

So basically we have StackPanel that is Vertically arranged which contains a Textbox (To Display Timer) and another Horizontally arranged StackPanel (Containing Buttons).

For Timer we have used DispatchTimer,

        #region Timer Methods

        private void StartTimer()
        {
            this.timer.Interval = new TimeSpan(0, 0, 1);
            this.timer.Tick += timer_Tick;
            this.timer.Start();
        }

        private void StopTimer()
        {
            this.timer.Tick -= timer_Tick;
            this.timer.Stop();
        }

        private void ResetTimer()
        {
            this.minutes = this.seconds = this.hours = 0;
            this.StopwatchText.Text = "0 : 0 : 0";
        }

        #endregion

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

#region Timer Methods

private void StartTimer()

{

this.timer.Interval = new TimeSpan(0, 0, 1);

this.timer.Tick += timer_Tick;

this.timer.Start();

}

private void StopTimer()

{

this.timer.Tick -= timer_Tick;

this.timer.Stop();

}

private void ResetTimer()

{

this.minutes = this.seconds = this.hours = 0;

this.StopwatchText.Text = "0 : 0 : 0";

}

#endregion

In StartTimer method we are setting the interval for DispatchTimer to 1 sec. So it means that a Tick event will be raised every 1 sec.

we listen to that event in ,

this.timer.Tick += timer_Tick;

Whenever the timer.tick event is raised we change the time on UI using this simple logic ,

  private void timer_Tick(object sender, object e)
        {
            //Just change the text  here

            ++this.seconds;
            if(this.seconds == 60)
            {
                this.minutes++;
                this.seconds = 0;
            }
            if(this.minutes == 60)
            {
                this.hours++;
                this.minutes = 0;
            }

            this.StopwatchText.Text = string.Format("{0} : {1} : {2}", hours,minutes, seconds);
        }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

private void timer_Tick(object sender, object e)

{

//Just change the text here

++this.seconds;

if(this.seconds == 60)

{

this.minutes++;

this.seconds = 0;

}

if(this.minutes == 60)

{

this.hours++;

this.minutes = 0;

}

this.StopwatchText.Text = string.Format("{0} : {1} : {2}", hours,minutes, seconds);

}

This event is triggered every second , so increment second value every time this event is triggered.

Then check if 60 seconds, reset the seconds to zero and set minute++, similarly for minutes and hour.

And for button click events of Start, Pause , and Stop we will just call the Timer methods mentioned above in following manner :

 private void Start_Click(object sender, RoutedEventArgs e)
        {
            if(!this.timer.IsEnabled)
            {
                this.StartTimer();
            }
        }

        private void Stop_Click(object sender, RoutedEventArgs e)
        {
            this.StopTimer();
            this.ResetTimer();
        }
         
        private void Pause_Click(object sender, RoutedEventArgs e)
        {
            if (this.timer.IsEnabled)
            {
                this.StopTimer();
            }
        }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

private void Start_Click(object sender, RoutedEventArgs e)

{

if(!this.timer.IsEnabled)

{

this.StartTimer();

}

private void Stop_Click(object sender, RoutedEventArgs e)

{

this.StopTimer();

this.ResetTimer();

}

private void Pause_Click(object sender, RoutedEventArgs e)

{

if (this.timer.IsEnabled)

{

this.StopTimer();

}

Screen shot of Stopwatch Timer App :

you can download the full code here : Stopwatch.

Author: algomaster

Find height of binary tree

Sum of all nodes in Binary tree

Binary Trees

Trees

Bubble Sort

Stopwatch Timer App Windows Phone

Recent Posts

Algotutor