Category Archives: Mixed

Binary Search Tree To Doubly Linked List

Binary Search Tree To Doubly Linked List

Convert Binary search tree to doubly linked list.

Note: BiNode – is a data structure that has two pointers to two nodes. It used to represent both data structure, a binary tree or doubly linked list.

Algorithm:
  1. Recursively go to left end
  2. Recursively go to right end
  3. If left child exists then
    1. Get to tail of left child
    2. Merge after root node after tail
  4. If Right child exists then
    1. Merge right child before root
  5. If left child exists then
    1. return left child
  6. Else
    1. return root

Latest Source Code:
Github: BinarySearchTreeToDoublyLinkedList.java


Output:

Tree InOrder: 8, 14, 20, 25, 40, 50, 100, 
DLL from head side: 8, 14, 20, 25, 40, 50, 100, 
DLL from Tail side: 100, 50, 40, 25, 20, 14, 8,