Binary Tree Post-Order Traversal - Recursive and Iterative Solution

 Posted on October 5, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Consider the tree: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root. Therefore, the Postorder traversal of the above tree will outputs: [Read More]
kodeknight  postorder  incomplete  binary-search-tree  BST  Postorder traversal 

Binary Tree In-Order Traversal - Recursive and Iterative Solution

 Posted on October 5, 2013  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Consider the tree Inorder traversal prints the binary tree in increasing order in case of Binary Search Tree, but here we are discussing any binary tree. To traverse a binary tree in Inorder, following operations are carried-out : Traverse the left most subtree starting at the left external node,  Visit the root, and Traverse the right subtree starting at the left external node. Therefore, the Inorder traversal of the above tree will outputs: [Read More]
inorder  Binary Tree  BT  kodeknight  incomplete  Inorder traversal 

Iterators - Allowing iteration over data structures (in java)

 Posted on September 10, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves. Here’s where java gives us the power called iterators which allows us to iterate over data structure. Design Challenge Consider the stack data structure and we want to support iteration over it on client side. [Read More]
kodeknight  incomplete  Data Structure  java 

Generic data structures in java

 Posted on September 10, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Suppose we have a stack of string, but later we want to use it for integers. We have to re-write the code again and again for every data type. So how can we solve this.

Attempt 1 - Creating the stack for every data type, which is very exhaustive and needs code changes again.

**Attempt 2 - **Implement a stack using Object class.
Example

Downside -

  • Discover type mismatch errors at run time
  • Casting has to be done at client side
  • Code looks ugly because of so many castings

Attempt 3 - Java generics

kodeknight  incomplete  generic classes  stack  java 

Random Contraction Algorithm

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

This algorithm was designed by Karger in 1990, as phd student at stanford. This algorithm is used to solve the min cut problem, which is : Input - An undirected graph G = (V,E) , (note that parallel edges are allowed) Goal - Tom compute a cut with fewest number of crossing edges (a min cut) Karger’s Algorithm We will have just one mail loop, and algorithm terminates when only 2 vertices are remaining. [Read More]
Graph  kodeknight  incomplete 

Graph Representations

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

We have already discussed what are graphs here. Now graph can be represented in 2ways: Adjacency matrix  Adjacency list Adjacency Matrix Undirected graph Represent G by a nXn, n being number of vertices 0-1 matrix A, where Aij = 1 for every edge between 2 nodes. Undirected graph with parallel edges Aij = b*1 where b is number of parallel edges between i and j. Weighted Undirected graph [Read More]
Graph  kodeknight  incomplete 

Integer Multiplication using Karatsuba algorithm

 Posted on August 14, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Normal Integer method If we consider the integer multiplication, we need 2 integers and output is also integer. Suppose we have to multiply 5678*1234. In the normal way, we will realize following: 5678 X 1234 \------------ 22712 //first number multiply as is i.e. 4\*5678 17034- //2nd time, shift (left) and then multiply the number as 3\*5678 11356-- //shift twice 5678--- //shift thrice \------------ 7006652 ```So, each time we multiply, depending on the digit of the 2nd number, we shift and then multiply. [Read More]
master-method  kodeknight  time complexity  divide and conquer  incomplete  multiplication