Keywords

.NET (3) .rb (1) *.cod (1) 3110c (1) Algorithm (1) Amazon Cloud Drive (1) amkette (1) Android (1) Apex (6) apex:dynamic (1) API (1) API version (1) Application Development Contest (2) Artificial Intelligence (2) Atricore (1) b2g (1) Binary Search Tree (1) Blackberry Application Development (1) Blackberry Java Development Environment (1) Blender Game Engine (1) bluetooth (2) Boot2Gecko (1) bug fix (1) C (1) C++ (2) Cloud computing (1) Cloud Storage (1) Code Blocks (1) Code for a Cause (2) codejam (1) Coding (1) const_cast (1) Custom Help (1) Dancing With the Googlers (1) Data Structures (1) desktop environment (5) Doubly Linked List (1) Dropbox (1) dynamic visualforce component (1) dynamic_cast (1) Enterprise WSDL (1) Execution Context (1) fedora 14 (1) fedora 17 (5) Firefox OS (1) Flashing Nokia 3110c handset (1) Force.com (7) Gaia (1) Game Developement (1) GCC (2) GDG (2) Goank (1) Google (4) Google Developer Group (2) Google Drive (1) GTK+ (5) HACK2012 (2) Hall of Mirrors (1) help for this page (1) HTML5 (2) HTTP Web Server (1) IDE (1) Identity Provider (1) Intelligent Systems (1) Java (1) JDE (1) JOSSO (1) location based social network (1) me.social (1) MinGW (1) Natural Language Processing (1) Natural Language Toolkit (1) neckphone (1) NLKT (1) Nokia Pheonix (1) Notebook (1) Numeric XML Tags (1) OAuth2.0 (1) OLPC (7) OLPC-XO-1 (7) One Laptop per Child (5) Override custom help (1) Paas (1) Partner WSDL (1) Polymorphism (1) programming contest (1) PyGTK (4) Python (10) Recycled Numbers (1) reinterpret_cast (1) Research (1) REST (1) RM-237 (1) Robotics (1) Ruby (1) Saas (2) Salesforce.com (7) SDK (1) Service Provider (1) Single sign on (1) SOAP (3) Speaking in Tongues (1) SSO Agent (1) SSO Gateway (1) static_const (1) sugar (7) sugar activity (4) sugarlabs (7) SVG (2) Symbiotic AI (1) Tabbed container (1) TCP/IP (1) TCP/IP stack (1) Typecasting (1) typeid (1) ubuntu 13.10 (1) UDP (1) Upgrade Assembly (1) Visualforce (2) Web Server (1) Web Services (3) Web2.0 (1) wikipedia (1) wikipediaHI (1) WSDL (1) XML tags (1)

Sunday, February 23, 2014

Algorithm Magic: Binary Search Tree to Doubly Linked List

Hi friends,

This post gives solution to a famous data structures problem: Converting a Binary Search Tree to Doubly Linked List. I am assuming you are well aware of what there data structures are and their behavior.

Lets jump into algorithm to convert this.

  • Since each subtree in a binary tree is a binary tree itself, we can use recursion for achieving this. We start by root node and reach leaf nodes. 
  • While traversing, we see if node does not have any left or right child, the node itself is returned. If it has non empty child nodes, then we create doubly linked list with 3 nodes( current node, left child node and parent node). 
  • Now here is the magic, the left child is not exactly its direct left child. Since our aim is to convert it into a sorted doubly linked list, we need to get the maximum value node which is less than current node value in left subtree as as left child for current node. Similarly, the node with least value in right subtree as right child of current node. 
  • That's it, apply this logic and solve it.
The class used to represent the node in binary tree and doubly linked list*:
*left will indicate previous node in doubly linked list and right will indicate the next node in doubly linked list.

function to insert node in BST:


function to convert BST to DLL:


function to show doubly linked list:




Here is the implementation of this algorithm: Download here.

Hope this helps you learn how to convert BST into DLL.
Cheers!