Convert Binary Tree to Doubly linked list in level order
Posted on May 16, 2015
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:
The output will be a double linked list like this:
Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.
[Read More]Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving
Posted on May 3, 2015
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position.
Example
Example 1
Input
s1 = abcd
s2 = bacd
Output
Ans = 1
Reason, just move b forward and we get it.
Example 2
Input
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Output
Ans =7
Explanation
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Characters b,e,g are in the order, rest characters have to brought first.
[Read More]Sorted Linked List to Balanced BST
Posted on February 26, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.
**Example : **
Input: Linked List 1->2->3->4->5->6->7 Output: A Balanced BST 4 / \\ 2 6 / \\ / \\ 1 3 4 7 Lets discuss 2 approaches for this problem.
Solution
Method 1 (Simple)
Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed.
[Read More]Convert sorted array to Balanced BST
Posted on February 26, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
Examples
Input: 1 2 3 4 5 6 7 Output: 4 / \\ 3 6 / \\ / \\ 3 4 6 7 Solutions ** Method 1 - Take the array’s middle element and insert it recursively**
Pick up the middle element of the array Set it as the root Recursively build up left and right subtrees with lower and higher halves of the array Here is the code in java:
[Read More]Create linked lists of all the nodes at each depth for a BST
Posted on February 10, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)
Example
So a binary tree such as :
(1) / \\ / \\ (2) (3) / \\ / \\ (4) (5) (6) (7) Will return linked lists:
(1) => NULL (2) => (3) => NULL (4) => (5) => (6) => (7) => NULL Solution
[Read More]Convert Binary tree to Binary Search Tree conversion in place
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Converting an Infix Expression to Postfix expression using a stack
Posted on September 10, 2013
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Pre-requisite - What is infix, postfix and prefix? Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. Postfix is also known as Reverse Polish Notation or RPN , and prefix expression is also known as Polish notation.
Infix - Operators are written in-between their operands. eg. A+B
Postfix - Operators are written after their operands. eg. AB+ Prefix - Operators are written before their operands. eg.
[Read More]Converting integers less than 100 to words
Posted on January 6, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
This is a classic problem in which we’re given an integer less than 100 and we have to output the words corresponding to the integer’s value. For instance, if input is 90, then the output is “ninety” Moreover, if the input is -99, then the output is “incorrect input”
To solve this problem, we should have arrays of unique names such as “one” and “thirteen”. The reason is that other integers’ names are made up of just those unique names.
[Read More]Convert Binary tree to double linked list in inorder traversal
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.
Example Input
[Read More]Convert integers to roman numbers
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Question: write an algorithm to convert an integer into roman number. For example, 1 -> I, 2 -> II, or 4 -> IV.
Solution: in order to solve this problem, we must know the rules of writing roman numerals. For example, I is 1 and V is 5 but IV is not 6 but 4 (5 -1). Moreover, there is no 0 number in roman numeral system. Here is the link to an article about roman numerals if you are unfamiliar with the system.
[Read More]