Unique Binary Search Trees

Problem Statement

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Continue reading


Path Sum in Binary Tree

Problem Statement

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Continue reading

Addition in Linked List

Problem Statement

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Continue reading

Loop in Linked List

Hi to all,

This is my first article in this blog. The article briefly describes How to Find a Loop in Linked List and Finding the start of the Loop.

To find the Loop in linked list, we can use Floyd’s Cycle Detection Algorithm. The algorithm is also Tortoise – Hare Algorithm. 

Concepts Behind Floyd’s:

Imagine a circular track and two runners. One runner is twice as fast as the other. Both of them start at same point  ‘P’. The only point they will meet in the circular track again is the start point ‘P’.

If the slow runner starts at “S” and fast runner starts at “K” distance away from the point “S”, then they will meet in the circular track at “K” distance before the start point “S”.

See this diagram for clear understanding,


The fast runner ‘F’ is quarter distance ahead of ‘S’.  ‘S’ is the starting point. They both meet quarter distance before the starting point ‘S’.

The point we derive from this is :

If  the faster runner is ‘K’ step ahead of the slow runner at the start of the race, then they meet first at ‘K’ Steps before the starting point.

You can have a better understanding , if u are able to crack this spoj problem .

Continue reading