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]Reverse the doubly linked list
Posted on April 18, 2015
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem Reverse the doubly linked list
Input
10 - 8 - 4 - 2
Output
2 - 4 - 8 - 12
Solution Method 1 - Reversing the prev and next references
Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the prev & next references in all the nodes of the list and need to make head point to the last node of original list (which will be the first node in the reversed list).
[Read More]Doubly linked list ADT
Posted on April 18, 2015
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
The beginning and ending nodes previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node.
[Read More]Bubble sort on double linked list
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Following can be the pseudocode:
public void bubbleSort() {
boolean done = false;
while (!done) {
Node cur = head;
done = true;
while(cur != tail) {
if (cur.getNext().getCount()>cur.getCount()) {
swap(cur.getNext(),cur);
done=false;
}
cur = cur.getNext();
}
}
}
Thanks.
Source : stackoverflow
Implementing doubly linked list using single pointer
Posted on August 8, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Convert Binary Tree to Double Linked List in Zig-Zag Order
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Question: given a binary tree, write an algorithm to convert the tree into a double-linked list. The list must be as if the tree is traversed in zig-zag and level order.
Solution: let’s first understand what the objective is. By zig-zag level order, the question means that we need to traverse the tree in level order, a.k.a breadth first, such that the next level is traversed in the oposite direction to the current level.
[Read More]Double Linked List Structure
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
If you wish to traverse a list both forwards and backwards efficiently, or if you wish, given a list element, to determine the preceding and following elements quickly, then the doubly-linked list comes in handy. A list element contains the data plus pointers to the next and previous list items as shown in the picture below.
Of course we need a pointer to some link in the doubly-linked list to access list elements.
[Read More]Vertical Sum of a Binary Tree
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
please explain doubly linked list method in words Anonymous - Apr 6, 2014please explain doubly linked list method in words
Added the basic algo for that:
1. Start with the root node and empty double list listNode
2. Add the value of the rootNode to the current listNode
3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
4. Similarly for right node
Please let me know if I have not explained it properly.
[Read More]Vertical Sum of a Binary Tree
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Question : Find vertical sum of given binary tree.
Example:
1 / \\ 2 3 / \\ / \\ 4 5 6 7 The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7
[Read More]How to reverse a doubly linked list ?
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
I talked about how to reverse a singly linked list earlier. That was slightly tricky to understand.
Reversing a doubly linked list is relatively easy. The logic is : You need to keep on changing the next and previous pointers as you traverse the entire list. Here is the code snippet in Java :
**public** **void** **reverse**() { **if** (first == **null**) **return**; DoubleNode previous = first; DoubleNode current = first.
[Read More]