Skip to main content

Posts

How to Find if Linked List contains Loops or Cycles in C#

In this post I will show you how to detect loop in linked list.We can find the loop in the linked list via Floyd’s Cycle-Finding Algorithm, explained here.The algorithm is pretty straightforward: We start at the beginning of the linked list with two pointers. The first pointer is incremented through each node of the list. The second pointer moves twice as fast, and skips every other node. If the linked list contains a loop, these two pointers will eventually meet at the same node, thus indicating that the linked list contains a loop. .using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Algo { public class Node { public Node Next { get; set; } public int Value { get; set; } public Node(int value) { this.Value = value; } } public class LinkedList { private Node _head; public LinkedList() { } public vo…

Reverse a given linked list in c#

In this post I will show you how to reverse a  given linked list in c#.For example a given linked list as show below10->20->30-NULLthen output should be30->20->10-NULLusing System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Algo { public class List { public List Next { get; set; } public int Value { get; set; } public List(int value) { Value = value; } public override string ToString() { List current = this; StringBuilder builder = new StringBuilder(); while (current!=null) { builder.Append(current.Value + "->"); current = current.Next; } return builder.ToString(); } public List ReverseList() { List prev = null; List next = null; List current = this; …

How to check a tree is a binary tree of not

This is continuation of my post How to create binary tree in c#.In this post I will show you how to check a given tree is a binary tree or not. public bool isBST() { return (IsBST(_root)); } private bool IsBST(Node node) { if (node == null) return (true); // do the subtrees contain values that do not // agree with the node? if (node.Left != null && FindMaxValue(node.Left) > node.Data) return (false); if (node.Right != null && FindMinValue(node.Right) <= node.Data) return (false); // check that the subtrees themselves are ok return (IsBST(node.Left) && IsBST(node.Right)); }

Mirror of a binary tree

This is continuation of my post How to create binary tree in c#.In this post I will show you how convert a given binary tree into it’s mirror image./**
Changes the tree into its mirror image. So the tree...
       4
      / \
     2   5
    / \
   1   3 is changed to...
       4
      / \
     5   2
        / \
       3   1Strategy:Uses a recursive helper that recurs over the tree, swapping the left/right pointers. public void MirrorTree() { MirrorTree(_root); } private void MirrorTree(Node node) { if (node != null) { // do the sub-trees MirrorTree(node.Left); MirrorTree(node.Right); // swap the left/right pointers Node temp = node.Left; node.Left = node.Right; node.Right = temp; } }

How to print out all path from root to leaf of a given binary tree

This is continuation of my post How to create binary tree in c#.In this post I will show you how to print all path from root to leaf of a given binary tree in c#.Let’s consider following binary tree.             *       4
             *    2     5
             *  1    3     For above tree there are three path from root to leafPath 1 : 4 2 1Path 2: 4 2 3Path 3: 4 5 public void PrintPath() { int[] path = new int[100]; printPaths(_root, path, 0); } private void printPaths(Node node, int[] path, int pathLen) { if (node == null) return; // append this node to the path array path[pathLen] = node.Data; pathLen++; // it's a leaf, so print the path that led to here if (node.Left == null && node.Right == null) { PrintArray(path, pathLen); } else { // otherwise try both subtre…

Given a binary tree, find path sum

Given a tree and a sum, returns true if there is a path from the root  down to a leaf, such that adding up all the values along the path  equals the given sum.let’s consider the following binary tree as an example and path sum value is 9.        4
      / \
     2   5
    / \
   1   3Root-to-leaf paths:
   path 1: 4 2 1
   path 2: 4 2 3
   path 3: 4 5You can see that there are two path that gives sum 9 (Path2 and Path 3).Traverse the tree from root to leaves in top down fashion and subtract the node value from the sum  and check to see if the sum is 0 when you run out of tree. public bool HasPathSum(int sum) { return HasPathSum(_root, sum); } private bool HasPathSum(Node root, int sum) { // return true if we run out of tree and sum==0 if (root == null) return sum == 0; else { int subSum = sum - root.Data; return ( HasPathSum(root.L…

How to find min or max value in a given binary tree

This is continuation of my post How to create binary tree in c#.In this post I will show you how to find max or min value in a given binary tree.Min Value: Loop down to find the leftmost leaf Max Value: Loop down to find the rightmost leaf public int FindMinValue() { return FindMinValue(_root); } private int FindMinValue(Node root) { if (root == null) return -1; else { Node current = root; while (current.Left!=null) { current = current.Left; } return current.Data; } } public int FindMaxValue() { return FindMaxValue(_root); } private int FindMaxValue(Node root) { if (_root == null) return -1; else { Node current = root; while (curre…